문제

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

문제 접근

2를 기준으로 거리를 적어야 하기 때문에 BFS를 생각했다.

문제를 풀며 깨달은 점

• 재귀 없이 반복문으로 stack에서 하나씩 뽑으면 거리에 따른 구분을 하기 까다롭다. stack 안에서 거리에 따라 내부에 리스트를 하나씩 추가해서 한다거나 해야할 것 같다.
  => 재귀로 BFS 구현했다.
• 방문하지 않은 곳 중에서 겹치는 부분이 중복되어 스택에 들어가는 문제가 발생해서 stack 변수를 set으로 구현했다.
• ans라는 정답을 적을 새로운 2차원 배열을 선언했다가 접근하지 못하는 0인 부분을 그대로 둬도 괜찮다는 점에서 처음 상태를 받은 2차원 배열을 재활용해서 정답을 기록하기로 했다.
• 문제를 꼼꼼히 읽지 않아 방문할 수 없는 부분은 -1로 표기하는 것을 놓쳤다. 마지막에 한번 더 2차원 배열을 탐색하며 visited가 0인 부분(초기 입력에서 0이 아니면서)을 -1로 업데이트해줬다.

코드

from sys import stdin
from collections import deque

input = stdin.readline


def bfs(s, d):
    next_stack = set([])
    while s:
        tmp = s.pop()
        g[tmp[0]][tmp[1]] = d
        visited[tmp[0]][tmp[1]] = 1
        for i in range(4):
            next = (tmp[0] + y[i], tmp[1] + x[i])  # y,x
            if next[0] >= n or next[0] < 0:
                continue
            if next[1] >= m or next[1] < 0:
                continue
            if g[next[0]][next[1]] == 0 or visited[next[0]][next[1]] == 1:
                continue
            next_stack.add(next)
    if next_stack:
        bfs(next_stack, d + 1)


n, m = map(int, input().split())  # 세로, 가로

g = []
for i in range(n):
    g.append(list(map(int, input().split())))
visited = [[0 for _ in range(m)] for _ in range(n)]
t = 0
for i in range(n):
    for j in range(m):
        if g[i][j] == 2:
            t = (i, j)  # y,x
            break
d = 0
stack = set([])
stack.add(t)
x = [0, 0, -1, 1]
y = [1, -1, 0, 0]

bfs(stack, 0)
for i in range(n):
    for j in range(m):
        if visited[i][j] == 0 and g[i][j] != 0:
            g[i][j] = -1

for i in range(n):
    for j in range(m):
        print(g[i][j], end=" ")
    print("")

복잡도 분석

시간 복잡도

채점결과 : 720ms

공간 복잡도

채점 결과 : 51660KB

학습포인트