[백준|파이썬] 13700: 완전 범죄 (실버1)

2023. 4. 11. 17:57·Problem Solving/백준
반응형
문제

https://www.acmicpc.net/problem/13700

 

13700번: 완전 범죄

첫째 줄에 N, S, D, F, B, K가 주어지고, K > 0인 경우에는 둘째 줄에 경찰서의 위치 l1, l2, …, lK가 주어진다. (1 ≤ S, D ≤ N ≤ 100000, 0 ≤ F, B ≤ 100000, 0 ≤ K ≤ N/2, S ≠ D ≠ l) 

www.acmicpc.net

 

 

🐍파이썬
import sys
from collections import deque
def bfs(cnt, x):
queue = deque()
queue.append((cnt, x)) #(이동횟수, 좌표x)
while queue:
cnt, x = queue.popleft()
dx = [x-b, x+f] #뒤로 이동한 좌표, 앞으로 이동한 좌표
for nx in dx:
if nx >= n or nx < 0: #벽에 부딪혔을 때 건너뛰기
continue
if game[nx] == "p": #경찰서 피해가기
continue
if game[nx] == "h": #집에 도착하면 이동횟수 리턴
return cnt
game[nx] = "p" #방문한 좌표는 "p"로 설정해 다시 방문하지 않게 한다.
queue.append((cnt+1, nx)) #(이동횟수+1, 새로운 좌표)
return "BUG FOUND" #집에 도착하지 못한 경우
n, s, d, f, b, k = map(int, sys.stdin.readline().split())
game = ["t"] * n
#털린 금은방
game[s-1] = "g"
#도둑의 집
game[d-1] = "h"
temp = []
#경찰서 배치
temp = list(map(int, sys.stdin.readline().split()))
for i in temp:
game[i-1] = "p"
cnt = 1
for i in range(n):
if game[i] == "g": #금은방에서부터 출발
print(bfs(cnt, i))

 

 

다른 풀이 방법

from collections import deque
def solve(N:int,S:int,D:int)->int:
global police,move
que = deque()
que.append(S)
ans = 0
check = [False]*(N+1)
while que:
ans += 1
for _ in range(len(que)):
now = que.popleft()
for moving in move:
nextPosition = now + moving
if nextPosition == D:
return ans
elif 0 < nextPosition <= N and not check[nextPosition] and not nextPosition in police:
check[nextPosition] = True
que.append(nextPosition)
return -1
N,S,D,F,B,K = map(int,input().split())
move = (F,-B)
if K:police = set(map(int,input().split()))
else: police = set()
ans = solve(N,S,D)
if ans == -1:
print('BUG FOUND')
else:
print(ans)

 

반응형

'Problem Solving > 백준' 카테고리의 다른 글

[백준|파이썬] 5014: 스타트링크 (실버1)  (0) 2023.04.12
[백준|파이썬] 1697: 숨바꼭질 (실버1)  (0) 2023.04.12
[백준|파이썬] 7569: 토마토 (골드5)  (0) 2023.04.12
[백준|파이썬] 21736: 헌내기는 친구가 필요해(DFS/BFS 풀이) (실버2)  (0) 2023.04.11
[백준|파이썬] 2667: 단지번호붙이기(DFS/BFS 풀이) (실버1)  (0) 2023.04.11
[백준|파이썬] 4963: 섬의 개수 (실버2)  (0) 2023.04.11
'Problem Solving/백준' 카테고리의 다른 글
  • [백준|파이썬] 1697: 숨바꼭질 (실버1)
  • [백준|파이썬] 7569: 토마토 (골드5)
  • [백준|파이썬] 21736: 헌내기는 친구가 필요해(DFS/BFS 풀이) (실버2)
  • [백준|파이썬] 2667: 단지번호붙이기(DFS/BFS 풀이) (실버1)
청량리 물냉면
청량리 물냉면
프로그래밍 공부를 하고 있습니다. 공부 내용 정리 겸 정보 공유를 목적으로 합니다.
    반응형
  • 청량리 물냉면
    노력중인 블로그
    청량리 물냉면
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 프로그래밍
        • Programming
        • C | C++
        • Java
        • Python
      • 웹 프로그래밍
        • HTML | CSS
        • JavaScript | TypeScript
        • React
        • Vue.js
        • Next.js
        • Spring & Spring Boot
        • JSP & Servlet
        • DB
      • 웹 프로젝트
        • 웹 프로젝트
        • 🥨스낵몰
        • 👨‍👨‍👧‍👧소셜 가계부
        • 🌜꿈 일기장
        • 🔮포트폴리오 사이트
        • 🏃‍♂️팀 프로젝트: 일정관리 프로그램
        • 📈팀 프로젝트: AI기반 주식 분석 플랫폼
        • 😺Just Meow It: 고양이의 조언
      • 앱 프로그래밍
        • Flutter
        • Kotlin
      • Problem Solving
        • 백준
        • 프로그래머스
        • SWEA
      • Computer Science
        • 알고리즘
        • 컴퓨터 네트워크
        • 이산수학
      • Developer
        • 후기
        • 자료정리
        • 취업 | 취준
        • 웹개발 교육 프로그램
        • TIL
  • 블로그 메뉴

    • 홈
    • Github
  • 공지사항

    • 프로그래밍 공부 중😊
  • 인기 글

  • 태그

    웹사이트
    컴퓨터네트워크
    알고리즘
    뉴렉처
    타입스크립트
    ZeroCho
    자바
    파이썬
    플러터
    백준
    리액트
    mysql
    프로그래머스
    자바스크립트
    Next.js
    Til
    프로젝트
    공식문서
    구현
    SWEA
    React
    AWS
    d3
    spring boot
    클론 프로젝트
    블로그 제작
    포트폴리오
    Jiraynor Programming
    bfs
    강의내용정리
  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
청량리 물냉면
[백준|파이썬] 13700: 완전 범죄 (실버1)

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.