[BOJ] 벽 부수고 이동하기 4 (16946, G2)

 

벽을 하나 부쉈을 때 그 자리에서 연결된 칸 수는 몇 칸인지 구하는 것이다.

생각보다 판이 좀 커질 수 있어서, 그냥 하나하나 다 구하기엔 당연히 TLE 걸릴 것이라 다른 방법이 필요하다.

그러면 벽 바로 상/하/좌/우 1칸을 기준으로 빈 연결된 공간의 개수를 더해주면 된다!

 

 

하면 틀린다. 빈 공간이 연결되어 있을 수 있다. 뭔 소리냐

1	1	1	1	1
1	0	0	1	1
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1

붉은 1을 잘 보면, 1을 부수면 6칸이 되어야 한다. 하지만 1에 연결되어 있는 상/하/좌/우 만 더하면
3 + 3 + 1 + 1 = 8칸으로 맞지 않는다. 무엇이 문제일까?

- 연결된 영역을 중복해서 세서는 안된다.
- 자기 자신도 포함해야 한다.

이 두 가지 문제를 어떻게 해결해야 할까?

BFS로 영역을 세는 문제는 많이 풀어보았을 것이다. 허나, 여기에 영역의 넓이를 단순히 적는 방법으로는 이를 구분할 수 없다.
지도에는 영역의 번호를 적는다. 하나의 연결된 영역에는 같은 번호를 붙인다.
그리고 별도의 dict를 선언하여 영역의 번호에, 그 영역의 넓이를 할당하면 끝.

그렇게 하면 부수려는 벽의 상/하/좌/우의 연결된 영역 번호를 set으로 해서 중복없이 더해주면 된다. 1 더하기 잊지 말고.

이를 코드로 작성하면 된다.

import sys
from collections import deque
input = sys.stdin.readline
mv_list = [[1, 0], [-1, 0], [0, 1], [0, -1]]
rows, cols = map(int, input().split())
visited = [[False for _ in range(cols)] for _ in range(rows)]
maps = []
answer_maps = [[0 for _ in range(cols)] for _ in range(rows)]
connected_dict = {}

for _ in range(rows):
    cur_row = list(str(input().rstrip()))
    cur_row = [int(x) for x in cur_row]
    cur_row = [-1 if x == 1 else x for x in cur_row]
    # 1칸짜리 빈 공간이 있어 벽과 구분이 불가능해서 벽을 -1로 치환할 거임    
    maps.append(cur_row)


def bfs(x, y, cur_area_num):
    global connected_dict
    count = 1
    queue = deque()
    queue.append([x, y])
    visited[x][y] = True
    maps[x][y] = cur_area_num
    
    while queue:
        cx, cy = queue.popleft()
        for mv in mv_list:
            nx, ny = cx + mv[0], cy + mv[1]
            if 0 <= nx < rows and 0 <= ny < cols:
                if not visited[nx][ny] and maps[nx][ny] == 0:
                    visited[nx][ny] = True
                    count += 1
                    maps[nx][ny] = cur_area_num
                    queue.append([nx, ny])
                    
    connected_dict[cur_area_num] = count
    return maps                

cur_area_num = 1
for i in range(rows):
    for j in range(cols):
        # 빈 공간일 경우
        if maps[i][j] == 0 and not visited[i][j]:
            maps = bfs(i, j, cur_area_num)
            cur_area_num += 1

# 마지막 정답 도출 과정.
for i in range(rows):
    for j in range(cols):
        # 벽일 경우 문제에 의해 0을 넣는다.
        if maps[i][j] != -1:
            answer_maps[i][j] == 0
        else:
            # 벽 주변의 연결 영역 파악, dict값을 가져올 것.
            # 이미 위에서 bfs로 -1 혹은 연결 번호를 1부터 붙여놨다.
            connect_list = []
            if i-1 >= 0:
                if maps[i-1][j] != -1:
                    connect_list.append(maps[i-1][j])
            if i+1 < rows:
                if maps[i+1][j] != -1:
                    connect_list.append(maps[i+1][j])
            if j-1 >= 0:
                if maps[i][j-1] != -1:
                    connect_list.append(maps[i][j-1])
            if j+1 < cols:
                if maps[i][j+1] != -1:
                    connect_list.append(maps[i][j+1])
            connect_list = list(set(connect_list))
            # 벽에 둘려싸여 아무것도 없다면, 자기 자신 1칸만 센다.
            if len(connect_list) == 0:
                answer_maps[i][j] = 1
            else:
                cur_sum = 1
                for c in connect_list:
                    cur_sum += connected_dict[c]
                answer_maps[i][j] = cur_sum % 10
        print(answer_maps[i][j], end = "")
    print()