백준 - 14940

문제 설명

주어진 지도에서 목표지점까지 거리를 구하는 문제로 n*m 크기의 지도가 주어지고, 각 지도에는 갈 수 있는 땅 1과 벽 0, 목표지점 2가 주어진다.

벽으로 둘러 쌓여져 있거나 목표지점에 도달할 수 없는 1은 -1로 표현한다.

예제

접근 방법

1. 효율적인 시간 구성을 위해 deque()를 사용
2. 지도에 존재하는 땅을 방문했다는 의미로 visit 배열 선언
3. 목표지점에 도달하지 못한 땅을 -1로 표현하기 위해 모든 값을 -1로 초기화 한 result 배열 선언
4. 목표지점 및 벽의 좌표 추출 후 result 배열 값에 0 할당
5. 목표지점부터 BFS를 수행하며, 상하좌우를 deque에 넣고, 하나씩 pop해서 사용
6. deque에는 지도에서 값이 1인 부분만 들어가도록 조건문 작성하여 벽과 혼동 없게끔 코드 작성
7. 방문한 땅은 visit 배열에 True를 할당하여 방문 처리

작성한 코드

틀린 코드

import sys
from collections import deque

input = sys.stdin.readline

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

land = []
queue = deque()
visit = [[False] * m for _ in range(n)]
result = [[-1] * m for _ in range(n)]

for i in range(n):
    row = list(map(int, input().split()))
    land.append(row)
    if 2 in row:
        queue.append([i, row.index(2), 0])  # 목표 지점 탐색
        visit[i][row.index(2)] = True

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

while(queue):
    y, x, z = queue.popleft()
    
    result[y][x] = z
    z += 1 

    if land[y][x] == 0:
        result[y][x] = 0
        continue

    for _ in range(4):
        ay = y+dy[_]
        ax = x+dx[_]
        if 0 <= ax < m and 0 <= ay < n:        
            if visit[ay][ax] == False:
                queue.append([ay, ax, z])
                visit[ay][ax] = True
for i in result:
    for j in i:
        print(j, end =' ')
    print()

벽에 대한 구분 및 거리 값을 명확하게 하지 못해 반례가 발생한 것으로 추정.

정답 코드

import sys
from collections import deque

input = sys.stdin.readline

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

land = []
queue = deque()
visit = [[False] * m for _ in range(n)]
result = [[-1] * m for _ in range(n)]

for i in range(n):
    row = list(map(int, input().split()))
    land.append(row)
    
    if 2 in row:
        queue.append([i, row.index(2)]) # 목표 지점 탐색
        visit[i][row.index(2)] = True
        result[i][row.index(2)] = 0
    
    for j in range(m):					# 벽 지점 탐색 
        if row[j] == 0:
            result[i][j] = 0

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

while(queue):
    y, x = queue.popleft()     

    for _ in range(4):					# 상하좌우 탐색
        ay = y+dy[_]
        ax = x+dx[_]
        
        if 0 <= ax < m and 0 <= ay < n: # 범위 확인
        	if not visit[ay][ax] and land[ay][ax] == 1: # 방문 확인    
            	queue.append([ay, ax])
            	visit[ay][ax] = True
            	result[ay][ax] = result[y][x] + 1

for i in result:
    for j in i:
        print(j, end =' ')
    print()