BOJ - 17129

백준 문제 링크
윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

❓접근법

1. BFS를 사용했다.
2. 초기값 INF = int(1e9), min_value = INF # 최단 거리를 찾을 변수
   정보섬 2층의 좌표를 start_x, start_y 로 받고
   answer = [[0] * m for i in range(m)]]으로 지정한다.
3. bfs 함수 내에서
   min_value를 global 처리 해주고,
   isCan = False로 지정한다. # 음식을 먹을 수 있는지 확인하는 변수
4. 4 방향동안 탐색을 하면서
   다음 좌표가 범위 안에 들고 아직 방문하지 않았을 때,

• 다음 좌표가 0 이라면

answer[nx][ny] = answer[x][y] + 1
queue.append((nx, ny))
visited[nx][ny] = True

• 다음 좌표가 [2, 3, 4, 5] 안에 있다면

answer[nx][ny] = answer[x][y] + 1
queue.append((nx, ny))
visited[nx][ny] = True
isCan = True
min_value = min(min_value, answer[nx][ny])

마지막으로는 isCan을 return 해준다.
5. bfs(start_x, start_y)를 했을 때,

• isCan == True 이면 'TAK' 와 min_value 를 출력한다.
• isCan == False 이면 'NIE' 를 출력한다.

👌🏻코드

from collections import deque

INF = int(1e9)

n, m = map(int, input().split())

graph = []
for _ in range(n):
    graph.append(list(map(int, input())))
    
dx = [0, 0, 1, -1]
dy = [1, -1 ,0 ,0]

start_x, start_y = 0, 0

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            start_x, start_y = i, j
            
            
min_value = INF
answer = [[0] * m for _ in range(n)]

def bfs(x, y):
    global min_value
    isCan = False
    
    queue = deque()
    queue.append((x, y))
    
    visited = [[False] * m for _ in range(n)]
    visited[x][y] = True
    
    while queue:
        x, y = queue.popleft()
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            
            if (0 <= nx < n) and (0 <= ny < m) and not visited[nx][ny] :
                
                if graph[nx][ny] == 0:
                    answer[nx][ny] = answer[x][y] + 1
                    queue.append((nx, ny))
                    visited[nx][ny] = True
                    
                elif graph[nx][ny] in [2, 3, 4, 5]:
                    answer[nx][ny] = answer[x][y] + 1
                    queue.append((nx, ny))
                    visited[nx][ny] = True
                    isCan = True
                    min_value = min(min_value, answer[nx][ny])
                    
    return isCan
    
    
if bfs(start_x, start_y) == True:
    print('TAK')
    print(min_value)
    
else:
    print('NIE')