728x90

2022.01.14

백준 1697 숨바꼭질

# 1697 숨바꼭질
from collections import deque

N, K = map(int,input().split())

# 리스트 인덱스에 점으로 이동하는 시간을 저장하기 위해서 arr생성
# x-1이 더 빠른 경우도 있기 때문에 가장 큰 값에서 +2해준다.
if N >= K:
    arr = [0] * (N+2)
else:
    arr = [0] * (K+2)
    
def bfs(x):
    queue = deque()
    queue.append(x)
    arr[x] = 0
    if x == K:   # N == K 같은 경우 0 리턴
        return 0
    while queue:
        a = queue.popleft()
        dx = [1,-1,a]
        for i in range(3):
            nx = a + dx[i]
            if 0 <= nx < len(arr) and arr[nx] == 0:
                queue.append(nx)
                arr[nx] = arr[a] + 1
bfs(N)
print(arr[K])

x와 K 값이 같을 때 값을 지정해주는 것과 arr의 범위를 잘 못 정해줘서

문제가 무엇일까 하고 한참을 쳐다보았었다.

728x90
저작자표시 비영리

'Algorithm' 카테고리의 다른 글

백준 15651 파이썬  (0) 2022.01.20
백준 15649 파이썬  (0) 2022.01.17
백준 1436 파이썬  (0) 2022.01.13
백준 1158 파이썬 (큐 풀이)  (0) 2022.01.13
백준 7569 파이썬  (0) 2022.01.12
728x90

2022.01.11

백준 7576 토마토

#7576
from collections import deque

M, N = map(int, input().split())
arr = []
for i in range(N):
    arr.append(list(map(int,input().split())))
    
def BFS(graph):
    queue = deque()
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 1:
                queue.append((i,j)) #토마토가 여러개 있을 때를 해결
    
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] == 0:
                    queue.append((nx,ny))
                    arr[nx][ny] = arr[a][b] + 1
            
BFS(arr)
R = []
for i in range(N):
    if 0 in arr[i]:
        R.append(0)
    else:
        R.append(max(arr[i]))
if 0 in R:
    print(-1)
else:
    print(max(R)-1)

토마토가 여러 개 존재하면 어떻게 풀지?라는 의문을 반복문을 통해 해결했더니 

다른 BFS 문제와 별다를 게 없었다. 또 다른 점이라면 출력 조건이 좀 많다는 점?

728x90
저작자표시 비영리

'Algorithm' 카테고리의 다른 글

백준 1181 파이썬  (0) 2022.01.12
백준 1085 파이썬  (0) 2022.01.11
백준 1018 파이썬  (0) 2022.01.11
백준 10951 파이썬  (0) 2022.01.10
백준 10871 파이썬  (0) 2022.01.10

+ Recent posts

티스토리툴바