백준2234 - 성곽 (비트마스킹 & DFS) Python

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

해당 문제는 좌표마다의 벽의 정보가 주어지고, 이를 활용하여 방의 개수, 가장 넓은 방의 넓이, 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구하는 문제다.

예시와 같이 좌표 0,0가 11 인 경우를 예를 들면, 11은 1 + 2 + 8 로 이루어진 수며 이는 동쪽을 제외한 모든 벽이 막혀있다고 볼 수 있다.

그리고 11을 이진수로 바꾸면 1011 비트로 표현할 수 있는데, 이는 순서대로 '남쪽', '동쪽', '북쪽', '서쪽' 벽의 유무를 표현하고 있다.

 

따라서 좌표마다 비트마스킹을 하여 벽의 유무를 파악하고, 벽이 존재하지 않는 경로를 따라 DFS 알고리즘을 통해 해당 좌표가 가진 방의 크기를 구해나가면 된다. 

 

풀이 과정은 다음과 같다.

먼저 문제에서 제시된 '하나의 벽을 제거한 경우, 가장 넓은 방의 크기'를 구하기 위해 '방의 갯수'와 '가장 넓은 방의 크기'를 구한다.

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
from collections import deque

def solution (data) :
  arr = [list(map(int, _str.split())) for _str in data]
  n,m = arr.pop(0)
  # 방향을 담은 배열 (서,북,동,남 순)
  directions = [[-1,0],[0,-1],[1,0],[0,1]]
  # 방문 여부를 담을 2차원 배열
  visited = [[0 for _ in range(n)] for _ in range(m)]
  좌표에 따른 방 번호를 담을 2차원 배열
  info = [[0 for _ in range(n)] for _ in range(m)]
  # 정답으로 제출할 변수
  room_num, max_size, remove_max_size = 0,0,0
  # 방 번호에 따른 방 크기를 담을 딕셔너리
  room_sizes = {}
  
  def DFS (y,x) :
    stack = deque([[x,y]])
    # 방 크기 변수
    dep = 0

    while stack :
      x,y = stack.pop()
      if visited[y][x] : continue
      
      # 방문한 경우 방문 기록과 해당 좌표의 방번호를 기록
      visited[y][x] = 1
      info[y][x] = room_num
      dep += 1
      
      for i in range(4) :
        # 비트마스킹을 활용하여 해당 벽이 존재하지 않는 경우 해당 경로로 이동함
        # 즉, i = 0 인 경우, door == 1 이며, 
        # arr[y][x] 가 1을 포함하는지 확인 후 없을 경우 서쪽으로 이동 가능하다고 우선 판단
        door = (1 << i)
        if not arr[y][x] & door == door :
          dx, dy = directions[i]
          nx, ny = dx + x, dy + y
          
          # 이후 해당 좌표가 유효한 좌표인지, 방문하지 않은 좌표인지 확인 후 stack에 추가
          if verify(nx,ny,n,m) and visited[ny][nx] == 0 :
            stack.append([nx,ny])
    
    return dep
  
  # 방문 기록이 없을 시 해당 좌표에서부터 DFS 실행
  for i in range(m) :
    for j in range(n) :
      if visited[i][j] == 0 :
        room_num += 1
        temp = DFS(i,j)
        max_size = max(temp, max_size)
        room_sizes[room_num] = temp
   


def verify (x,y,X,Y) : 
  return 0 <= x < X and 0 <= y < Y
       
solution(input_data)

 

'방의 갯수'와 '가장 넓은 방의 크기'를 구했다면, 벽을 하나 부쉈을 경우의 최대 방의 크기를 구하는 것 또한 가능하다.

for i in range(m) :
    for j in range(n) :
      for k in range(4) : 
        # DFS에서 사용된 로직과 달리, 벽이 있는 경우 아래 로직을 실행
        door = (1 << k)
        if arr[i][j] & door == door :
          dx, dy = directions[k]
          # 다음 좌표
          nx, ny = dx + j, dy + i
          # 유효한 좌표인지 확인하며, 현재 좌표와 다음 좌표의 방 번호가 다르다면 실행
          # 이때 불필요하게 DFS를 실행할 필요없이 방 번호에 따른 방 크기를 저장해둔 딕셔너리에서
          # 두 좌표가 가진 방 번호로 방 크기를 합하여 계산
          if verify(nx, ny, n, m) and info[i][j] != info[ny][nx]:
            remove_max_size = max(room_sizes[info[i][j]] + room_sizes[info[ny][nx]], remove_max_size)

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
from collections import deque

def solution (data) :
  arr = [list(map(int, _str.split())) for _str in data]
  n,m = arr.pop(0)
  directions = [[-1,0],[0,-1],[1,0],[0,1]]
  visited = [[0 for _ in range(n)] for _ in range(m)]
  info = [[0 for _ in range(n)] for _ in range(m)]
  room_num, max_size, remove_max_size = 0,0,0
  room_sizes = {}
  
  def DFS (y,x) :
    stack = deque([[x,y]])
    dep = 0

    while stack :
      x,y = stack.pop()
      if visited[y][x] : continue
      
      visited[y][x] = 1
      info[y][x] = room_num
      dep += 1
    
      for i in range(4) :
        door = (1 << i)
        if not arr[y][x] & door == door :
          dx, dy = directions[i]
          nx, ny = dx + x, dy + y
          
          if verify(nx,ny,n,m) and visited[ny][nx] == 0 :
            stack.append([nx,ny])
    
    return dep
  
  for i in range(m) :
    for j in range(n) :
      if visited[i][j] == 0 :
        room_num += 1
        temp = DFS(i,j)
        max_size = max(temp, max_size)
        room_sizes[room_num] = temp
   
  for i in range(m) :
    for j in range(n) :
      for k in range(4) : 
        door = (1 << k)
        if arr[i][j] & door == door :
          dx, dy = directions[k]
          nx, ny = dx + j, dy + i
          if verify(nx, ny, n, m) and info[i][j] != info[ny][nx]:
            remove_max_size = max(room_sizes[info[i][j]] + room_sizes[info[ny][nx]], remove_max_size)
            
  print(room_num)
  print(max_size)
  print(remove_max_size)

def verify (x,y,X,Y) : 
  return 0 <= x < X and 0 <= y < Y
       
solution(input_data)

 

구현해야 할 내용이 많아서 그런가, 문제를 해결하며 어떻게 더 효율적이고 가독성 있게 작성할 수 있을까 고민했던 문제였다. 

때문에 풀이 시간도 길었지만, 그만큼 이해하고 깨닫는 부분도 많이 존재했기에 여러모로 이로웠던 문제이기도 하다. ^_^