[BaekJoon] "DFS/BFS" - 백준 14940번 문제 : 쉬운 최단 거리

[문제 설명]

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

14940번: 쉬운 최단거리

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하기

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있음

0은 갈 수 없는 땅, 1은 갈 수 있는 땅, 2는 목표 지점. 입력에서 2는 단 한개임

 

[해결 로직]

- 목표 지점이 2이기 때문에 2부터 시작을 함

- 그러면 2 바로 옆에 있는 곳은 1만큼의 거리가 생기기 때문에 2로부터 시작해서 탐색 시작

- 입력된 맵에서 2 발견시, 위치를 큐에 넣고 방문 표시를 해줌. 그리고, 출발하는 곳이니깐 맵에서 다시 0으로 표시

- 상하좌우 탐색을 하면서 맵 범위를 벗어나거나 이미 방문한 곳이면 패스

- 갈 수 있는 땅이라면 이전의 배열 값 +1 해주고, 위치를 큐에 삽입, 방문 표시를 해줌

- 탐색 다 하고 난 이후에 전체를 한번씩 돌면서 갈수 있는 땅인데 방문 표시가 되어 있지 않다면 -1로 표시 (땅인 부분 중에서 도달할 수 없는 위치임)

 

[Solution 코드]

from collections import deque
n,m = map(int, input().split())

ary = []
visited = [[0 for _ in range(m)] for _ in range(n)]
## 여기 사이즈 조절 잘 해줘야함!
## 이것때문에 계속런타임에러 발생하 뮤ㅠㅠ

for i in range(n):
    ary.append(list(map(int, input().split())))
    
q = deque()

for i in range(n):
    for j in range(m):
        if ary[i][j] == 2:
            q.append((i,j))
            visited[i][j] = 1 ## 방문 표시
            ary[i][j] = 0 ## 출발하는 곳이니깐 0으로 초기화

dx = [0,0,1,-1]
dy = [1, -1, 0, 0]

while q:
    cx, cy = q.popleft()

    for i in range(len(dx)):
        nx = cx + dx[i]
        ny = cy + dy[i]

        if nx < 0 or nx >= n or ny < 0 or ny >= m or visited[nx][ny] == 1:
            ## 범위를 벗어나거나, 이미 방문된 곳
            continue

        ## 위의 조건에 모두 해당 되지 않으면
        if ary[nx][ny] == 1: ## 진입 가능한 곳
            ary[nx][ny] = ary[cx][cy] + 1
            q.append((nx,ny))
            visited[nx][ny] = 1

for i in range(n):
    for j in range(m):
        if ary[i][j] != 0 and visited[i][j] == 0: ## 값 변경이 안된곳 = 진입불가
            ary[i][j] = -1
        print(ary[i][j], end = " ")
    print('')