[백준/2234] 성곽 (Python)

Problem : https://www.acmicpc.net/problem/2234

2234번: 성곽

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:12:38

 

---

 

문제 설명

 

대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.

성은 M × N(1 ≤ M, N ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

 

 

입력 및 출력

 

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

 

출력

첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.

 

입력 예시

7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

 

출력 예시

5
9
16

 

 

---

 

풀이

 

전체 지도를 일정 기준에 따라 그룹화하기 문제는 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)

풀이 완료~