첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.
전체 지도를 일정 기준에 따라 그룹화하기 문제는 DFS, BFS의 단골이라고 볼 수 있다. 또한 친절하게도, 경로 탐색을 제한하는 방향 정보를 숫자로 표시해 주었다. 서북동남 순으로 비트마스킹 연산을 시행하면 진행 여부를 빠르게 판별 가능하다.
즉 다음과 같은 순으로 문제를 풀이해 볼 수 있다.
방문하지 않은 모든 노드들에 대해 경로 탐색을 시행한다. 탐색 결과 방문한 노드의 수는 그 영역의 넓이가 되므로 이를 저장하도록 한다. 경로 탐색 방향은 앞서 말했듯 비트마스킹으로 판단 가능하다.
그렇다면, 첫 번째 문제와 두 번째 문제의 답을 바로 구할 수 있다.
성에 있는 방의 개수 : 경로 탐색이 호출된 횟수
가장 넓은 방의 넓이 : 저장된 방문 노드 수 리스트의 최댓값
마지막으로 세 번째 문제 역시 쉽게 구할 수 있다. 임의의 인접한, 그리고 서로 다른 영역 1, 2에 속하는 두 노드를 생각해 보자. 두 노드 사이의 벽을 허문다면, 새로운 영역의 넓이는 (영역 1의 넓이) + (영역 2의 넓이)가 된다. 즉 위 조건을 만족하는 모든 노드를 고려하여 최댓값을 구하면 된다.
풀이 코드
import sys
input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
M, N = map(int, input().split())
map_list = [list(map(int, input().split())) for _ in range(N)]
visited = [[-1]*M for _ in range(N)]
area_list = list()
def dfs(x, y, num) :
q = [(x, y)]
result = 1
while q :
x, y = q.pop()
for k in range(4) :
if map_list[y][x] & (1 << k) :
continue
ax, ay = x + dx[k], y + dy[k]
if -1 < ax < M and -1 < ay < N and visited[ay][ax] == -1 :
visited[ay][ax] = num
q.append((ax, ay))
result += 1
area_list.append(result)
cnt = 0
for i in range(N) :
for j in range(M) :
if visited[i][j] == -1 :
visited[i][j] = cnt
dfs(j, i, cnt)
cnt += 1
print(cnt)
print(max(area_list))
result = 0
for i in range(N) :
for j in range(M) :
for k in range(4) :
ai, aj = i + dy[k], j + dx[k]
if -1 < aj < M and -1 < ai < N and visited[i][j] != visited[ai][aj] :
result = max(result, area_list[visited[ai][aj]] + area_list[visited[i][j]])
print(result)
