반응형
문제
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 |