[백준] 14940번: 쉬운 최단거리 (파이썬)

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

 

전에 풀어봤던 bfs문제와 거의 똑같은 문제였다.

from collections import deque

n,m = map(int,input().split()) #n:세로,m:가로
arr = [] #입력받을 list
visited = [ [ -1 for i in range(m)] for j in range(n)] #방문 여부 list
#위, 왼, 아래, 오 순서
dx = [0,-1,0,1]
dy = [1,0,-1,0]

#BFS
def bfs(i,j):
    queue = deque()
    queue.append((i,j)) #큐에 넣기
    visited[i][j] = 0 #방문처리

    while queue: #큐가 빌 때까지
        x,y = queue.popleft()

        for t in range(4):
            nx, ny = dx[t] + x, dy[t] + y

            if 0 <= nx < n and 0<= ny < m and visited[nx][ny] == -1:
                if arr[nx][ny] == 0: # 갈 수 없는 땅 체크
                    visited[nx][ny] = 0
                elif arr[nx][ny] == 1: #갈 수 있는 땅 체크
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx,ny))
#입력 받기
for i in range(n):
    temp = list(map(int,input().split()))
    arr.append(temp)

for i in range(n):
    for j in range(m):
        if arr[i][j] == 2 and visited[i][j] == -1: #2를 만나면 bfs실행
            bfs(i,j)

#출력 하기
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            print(0, end=' ')
        else:
            print(visited[i][j], end=' ')
    print()

 

이해하기 쉽게 코드를 분리해서 보겠다.

from collections import deque

n,m = map(int,input().split()) #n:세로,m:가로
arr = [] #입력받을 list
visited = [ [ -1 for i in range(m)] for j in range(n)] #방문 여부 list
#위, 왼, 아래, 오 순서
dx = [0,-1,0,1]
dy = [1,0,-1,0]

bfs를 사용할 것이므로 deque 라이브러리를 불러온다.

입력받을 list와 방문여부를 기록할 list를 만든다.

 

#BFS
def bfs(i,j):
    queue = deque()
    queue.append((i,j)) #큐에 넣기
    visited[i][j] = 0 #방문처리

    while queue: #큐가 빌 때까지
        x,y = queue.popleft()

        for t in range(4):
            nx, ny = dx[t] + x, dy[t] + y

            if 0 <= nx < n and 0<= ny < m and visited[nx][ny] == -1:
                if arr[nx][ny] == 0: # 갈 수 없는 땅 체크
                    visited[nx][ny] = 0
                elif arr[nx][ny] == 1: #갈 수 있는 땅 체크
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx,ny))

bfs에선 우선 queue를 정의하고 i,j를 큐에 넣은 후 방문처리를 한다.

이후 해당 위치에서 위, 왼쪽, 아래, 오른쪽을 방문 가능한지 확인하고 큐가 빌 때까지 반복한다.

#입력 받기
for i in range(n):
    temp = list(map(int,input().split()))
    arr.append(temp)

for i in range(n):
    for j in range(m):
        if arr[i][j] == 2 and visited[i][j] == -1: #2를 만나면 bfs실행
            bfs(i,j)

#출력 하기
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            print(0, end=' ')
        else:
            print(visited[i][j], end=' ')
    print()

arr에서 2를 찾으면 bfs를 실행한다.

DFS, BFS는 비슷한 유형이 많은 것 같다.

문제를 많이 풀어보는 게 역시 중요한 것 같다.