14940

날짜 : 2023. 07. 15

사용 언어 : python

 

문제

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

 

 

코드

import sys
from collections import deque


def bfs(r, c):
    queue = deque()
    queue.append([r, c])
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx in range(n) and ny in range(m) and not visited[nx][ny] and graph[nx][ny] == 1:
                visited[nx][ny] = True  # 방문처리
                graph[nx][ny] = graph[x][y] + 1
                queue.append([nx, ny])
    return


n, m = map(int, sys.stdin.readline().split())  # 세로, 가로
graph = list()
visited = [[False] * m for _ in range(n)]

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            graph[i][j] = 0
            visited[i][j] = True
            bfs(i, j)
            break
    else: continue
    break

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and not visited[i][j]:  # 방문할 수 없는 경우
            graph[i][j] = -1

for row in graph:
    print(*row)

 

 

풀이

- 일반적인 BFS 풀이방식으로 문제를 해결한다.

- 다만, 방문할 수 없는 케이스가 발생할 수 있기 때문에 출력하기 전, 완전탐색 후 방문되지 않았고, 밟을 수 있는 케이스의 경우에 전부 -1처리를 한다.

 

 

알게된 점

- -1처리를 하는 부분을 뛰어넘어서 문제를 풀었기 때문에 거기서 오답이 발생했다.

- 그 이외에는 평이하게 해결할 수 있었다.

 

 

참고 사이트

-