[DFS, BFS] 백준 16946번: 벽 부수고 이동하기 4 / 골드 2

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

16946번: 벽 부수고 이동하기 4

import sys
input = sys.stdin.readline

x_lim, y_lim = map(int, input().split())
graph = [[x for x in input()] for _ in range(x_lim)]
visit = [['0']*y_lim for _ in range(x_lim)]
wall_visit = [['0']*y_lim for _ in range(x_lim)]
answer = [[0]*y_lim for _ in range(x_lim)]

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

for x in range(x_lim):
    for y in range(y_lim):
        if graph[x][y] == '1':
            answer[x][y] += 1
        if graph[x][y] == '0':
            graph[x][y] = 'F'
            count = 1
            walls = []
            q = [[x, y]]
            while q:
                cur_x, cur_y = q.pop()
                for i in range(4):
                    nx = cur_x + dx[i]
                    ny = cur_y + dy[i]
                    if 0 <= nx < x_lim and 0 <= ny < y_lim:
                        if graph[nx][ny] == '1'and wall_visit[nx][ny] == '0':
                            wall_visit[nx][ny] = 1
                            walls.append([nx, ny])

                        elif graph[nx][ny] == '0' and visit[nx][ny] == '0':
                            graph[nx][ny] = 'F'
                            visit[nx][ny] = '1'
                            q.append([nx, ny])
                            count += 1

            for i in range(len(walls)):
                pos_x, pos_y = walls[i]
                answer[pos_x][pos_y] += count
                wall_visit[pos_x][pos_y] = '0'

for i in range(x_lim):
    result = ''
    for j in range(y_lim):
        result += str(answer[i][j] % 10)
    print(result)

시간 초과에 걸리지 않기 위해선 한번 방문한 0의 영역은 다시 bfs를 돌 지 않도록 구현해야 한다.

 

그래서 나는 이중반복문을 돌면서 0인 곳을 만났을 경우 bfs를 통해 0이 그 구역에 몇 개가 있는 지 카운트 하면서 벽을 만났을 땐 wall 리스트에 넣어주었다. 

처음엔 이렇게 해도 시간 초과가 발생했는데 그 이유는

 

wall 리스트에 중복으로 wall 정보가 들어가지 않도록 조건문을 통해 기존 리스트에 없을 경우에만 wall 정보를 넣는다는 식으로 코드를 짰는데 이러면 wall 리스트 전체를 한번 돌아야 하므로 시간이 오래 걸린다. 

그래서 wall_visit이라는 2차원배열을 하나 더 만들어서 wall 방문 여부를 만들었다. 그래서 통과할 수 있었다.