실버 I

💡문제 분석 요약

BFS

💡알고리즘 설계

BFS를 통해 구현했다.

2인 항목을 찾아서 queue에 먼저 넣는다.

위 아래 오른쪽 왼쪽의 x,y값을 확인한다.

vistied를 통해 방문 여부를 체크하고, 방문하지 않았고+값이 1이라면 queue에 넣어준다.

만약 방문하지 않았는데 갈 수 있는 땅이라면, 값을 -1로 바꿔주고 출력한다.

💡코드

import sys, collections
queue = collections.deque()
input= sys.stdin.readline
n,m = map(int,input().strip().split())
x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
visited = [[False for _ in range(m)]for _ in range(m)]
maps = []
for _ in range(n):
    maps.append(list(map(int,input().strip().split())))

for i in range(n):
    for j in range(m):
        if maps[i][j]==2:
            queue.append([i,j,0])
            
while queue:
    x,y,distance = queue.popleft()
    if visited[x][y] == True:
        continue
    visited[x][y] = True
    maps[x][y] = distance
    new_distance = distance+1
    for i in range(4):
        dx = x+x1[i]
        dy = y+y1[i]
        if 0<=dx<n and 0<=dy<m and visited[dx][dy]==False and maps[dx][dy]==1:
            queue.append([dx,dy,new_distance])
for i in range(n):
    for j in range(m):
        if visited[i][j]==False and maps[i][j]==1:
            maps[i][j]=-1
        print(maps[i][j],end=' ')
    print()

💡 헷갈린 이유

visited를 쓰지 않고 구현하려고 했지만 거리가 1인 경우가 있어 무한 루프가 됨.
방문하지 않아서 queue에 넣었지만 방문하지 않은 상태가 유지되므로, dx,dy값이 중복되어 queue에 같은 값이 들어가서 탐색하는 경우가 발생됨. 따라서 visited가 True인지 확인하는 구문을 맨 위에 추가→ 이게 아니면 visited를 queue에 추가한 뒤 바로 True로 바꿀 수도 있음.
갈 수 있는 땅이지만 갈 수 없는 경우를 고려하지 않음