문제
대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.
이 성에 있는 방의 개수
가장 넓은 방의 넓이
하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.
성은 m×n(1 ≤ m, n ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.
입력
첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.
출력
첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.
🤔 생각
-
단지 찾기 문제의 응용 버전이라 할 수 있겠다.
-
숫자에 따라 방향이 달라지는 부분이 조금 까다로워 보이지만, 비트마스킹 체크값에 따라 방향을 설정해주면 된다.
-
1,2는 그냥 짜면 되는거고, 어려운건 3번이었다.
-
따로 bfs 더 돌릴 필요 없이, 각 방의 영역 넓이와 이웃 정보만 알고 있다면 단순 덧셈 비교로 3번 풀이가 가능하다.
-
영역마다 다른 값으로 마스킹하고, 이후에 인접 좌표의 마스킹 값을 비교하면서 덧셈 최댓값을 구하면 그게 3번 답이 되겠다.
이 영역 마스킹 개념을 생각해내는게 핵심이었던것 같다. 떠올리는데 20분은 족히 걸린것 같다...
📌 내 풀이
import sys
input = sys.stdin.readline
def bfs(a,b,mask):
q = [(a,b)]
masked[a][b] = mask
cnt = 1
while q:
tmp = []
for x,y in q:
for i in range(4):
if naive[x][y] & (1 << i): continue
nx, ny = x+move[i][0], y+move[i][1]
if 0 <= nx < m and 0 <= ny < n:
if masked[nx][ny] != -1: continue
masked[nx][ny] = mask
tmp.append((nx, ny))
cnt += 1
q = tmp
return cnt
n,m = map(int, input().split())
naive = tuple(tuple(map(int, input().split())) for _ in range(m))
masked = [[-1]*n for _ in range(m)]
move = tuple(((0,-1), (-1,0), (0,1), (1,0)))
area = []
rooms = 0
for i in range(m):
for j in range(n):
if masked[i][j] == -1:
area.append(bfs(i,j,rooms))
rooms += 1
combined = 0
for i in range(m):
for j in range(n):
if i and masked[i-1][j] != masked[i][j]:
combined = max(combined, area[masked[i-1][j]] + area[masked[i][j]])
if j and masked[i][j-1] != masked[i][j]:
combined = max(combined, area[masked[i][j-1]] + area[masked[i][j]])
print(rooms)
print(max(area))
print(combined)
마지막 반복문에서 range(1,m)으로 해두고 했더니 테스트 케이스는 통과하지만 틀렸습니다가 나온다.
어떻게 잘 게싱해서 통과되긴 했는데, 저게 왜 문제였는지 계속 고민했다.
아무래도 (0,0) 좌표가 간과되기 때문에 그런것 같다. 새삼 테스트 케이스가 치밀하다고 생각했다.
✔ 회고
- 격자에서 결합 넓이를 구할 때는 영역 마스킹을 떠올리자!
