백준 16946번: 벽 부수고 이동하기4(Python, 파이썬, BFS, 자료구조)

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.

• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

잘못된 문제 풀이

1.벽들의 좌표 저장

2.좌표 하나씩 꺼내서, 거기서 BFS 실행 후, 카운팅

3.카운팅한 값 % 10 해서 저장

너무 쉽다고 생각했는데, 당연히 시간초과...

오답 코드

import sys
from collections import deque

N, M = map(int,sys.stdin.readline().split())

maps = []

for _ in range(N):
    row = str(sys.stdin.readline().strip())
    maps.append(list(map(int,row)))

#for map in maps:
    #print(map)

wall_list = []
for x in range(N):
    for y in range(M):
        if maps[x][y] == 1:
            wall_list.append([x,y])

#for wall in wall_list:
#    print(wall)

answer_maps = [[0 for _ in range(M)] for _ in range(N)]

#for answer_map in answer_maps:
#    print(answer_map)

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

def bfs(coor_x, coor_y):
    global answer_maps
    visited = [[False for _ in range(M)] for _ in range(N)]
    queue = deque()
    queue.append([coor_x,coor_y])
    visited[coor_x][coor_y] = True
    count = 1

    while queue:
        sx, sy = queue.popleft()
        for i in range(4):
            nx = sx + dx[i]
            ny = sy + dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and maps[nx][ny] != 1:
                queue.append([nx,ny])
                visited[nx][ny] = True
                count += 1
        
    answer_maps[coor_x][coor_y] = count % 10

for wall_coor in wall_list:
    x, y = wall_coor[0], wall_coor[1]
    bfs(x,y)

#for answer_map in answer_maps:
#    print(answer_map)

for answer_map in answer_maps:
    for answer in answer_map:
        print(answer, end='')
    print()

문제 풀이

1. 빈 공간들은 미리 체크해놓는다. -> 빈 공간들을 묶고 번호를 부여

2.벽을 부쉈을 때, 어떤 빈공간과 이어지는지 체크하고 빈공간의 공간 개수 +해서 저장

정답 코드

import sys
from collections import deque

N, M = map(int,sys.stdin.readline().split())

maps = []

for _ in range(N):
    row = str(sys.stdin.readline().strip())
    maps.append(list(map(int,row)))

#for map in maps:
    #print(map)
area_index = [[0 for _ in range(M)] for _ in range(N)]
area_size = dict()

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

def bfs(coor_x, coor_y, index):
    global visited
    global area_index
    visited[coor_x][coor_y] = True
    count = 1
    queue = deque()
    queue.append([coor_x,coor_y])
    area_index[coor_x][coor_y] = index

    while queue:
        sx, sy = queue.popleft()
        for i in range(4):
            nx = sx + dx[i]; ny = sy + dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and maps[nx][ny] == 0 :
                queue.append([nx,ny])
                visited[nx][ny] = True
                count += 1
                area_index[nx][ny] = index
    area_size[index] = count

index = 1
visited = [[False for _ in range(M)] for _ in range(N)]
for x in range(N):
    for y in range(M):
        if not visited[x][y] and maps[x][y] == 0:
            bfs(x,y, index)
            index += 1

result = [[0 for _ in range(M)] for _ in range(N)]
for x in range(N):
    for y in range(M):
        if maps[x][y] == 1:
            result[x][y] += 1
            sets = set()
            for i in range(4):
                nx = x + dx[i]; ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < M and maps[nx][ny] == 0:
                    sets.add(area_index[nx][ny])
            for set_i in sets:
                result[x][y] += area_size[set_i]

for r in result:
    for value in r:
        print(value % 10 , end='')
    print()