백준 2234 : 성곽

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

2234번: 성곽

https://github.com/HPYoo/swcodingtest/commit/fbb832d08e1d2152e4ec5ff7f103554f24751e42

sw coding 2234 update(Baekjoon) · HPYoo/swcodingtest@fbb832d

1. 이진수의 각 비트라고 생각하면 쉽다?

 각 지점에 설치되어 있는 벽을 서(1) 북(2) 동(4) 남(8) 로 정의하여 그 총합으로 나타낸 결과를 정수로 표현하였다. 이 표현이 정말 이해하기 어려워서 처음에 풀때는 16개의 정보를 조합함수를 반복적으로 사용해서 푸려고 했다. 하지만, 이진수로 표현하는 것도 이내 어렵지 않게 구상할 수 있었다. 0부터 15까지 하나씩 꺼내서 2로 나누어서 나머지를 이용하면 이진수 조합을 쉽게 만들 수 있다. 방향벡터 dx, dy 의 정보 순서를 (서, 북, 동, 남) 으로 설정했기 때문에 인덱싱 할 때 어렵지 않게 접근이 가능하다.

w_dict = {}
for i in range(16):
    num = i
    temp_direction = [0, 0, 0, 0]
    it = 0
    while num > 0 :
        remain = num % 2
        temp_direction[it] = remain
        num //= 2
        it += 1
    w_dict[i] = temp_direction

# 서, 북, 동, 남 : 1, 2, 4, 8
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]

2. BFS 구현

 -1) 방의 개수 구하기
 -2) 방이 제일 큰 것 구하기
   -1) 과 -2) 의 경우는 흔한 BFS 문제기 때문에 어렵지 않게 구현할 수 있었다. 늘 하던대로 작성했다. 다만, 
   해결하기 어려웠던 문제는 -3) 이다.
 -3) 벽을 하나 없앴을 때 최대 방 크기 구하기
   엄청나게 괴롭힌 조건.
   가장 처음으로 생각한 아이디어는 모든 벽을 하나씩 지워가며 BFS를 추가적으로 돌리는 것이다. 하지만, 큐가 추가적으로 생성됨에 따라서 메모리 초과 & 시간 초과가 날 수 있다는 문제가 있다.
   그 다음으로 생각한 아이디어는 -1) 과정에서 영역들을 표시해줄 수 있는 배열(문제풀때는 regime이라고 정의함)을 새로 만들어주는 것이었다. 예제를 기준으로 생각해보면 다음과 같이 영역들을 구분할 수 있다. 해당 그림과 같이 배열로 저장한다음에 행 / 열 기준에 따라 영역이 변하는 구간을 따로 체크해주었다. 해당 그림 상황에서는 [1,2], [2,3], [3,4], [1,5], [3,5] 와 같이 인접한 영역끼리 리스트를 만들어 줄 수있다. 이렇게 만들면 반복문을 돌면서 각각의 영역의 합을 구할 수 있고, 최대크기를 구할 수 있다.
 ※ 여기에서 한 가지 실수를 했는데, 행을 기준으로만 인접 영역을 구하고 열에 대해서 구하지 않았었다. 이 사소한 실수찾는데 굉장히 오래걸렸는데, 이런 실수를 줄일 수 있도록 하자.

3. 전체코드

메모리 : 115980 KB, 시간 : 1624 ms, 풀이시간 : 2:12:34

N, M = map(int, input().split())
w_info = [list(map(int, input().split())) for _ in range(M)]

# Wall의 경우의 수 총 16개
w_dict = {}
for i in range(16):
    num = i
    temp_direction = [0, 0, 0, 0]
    it = 0
    while num > 0 :
        remain = num % 2
        temp_direction[it] = remain
        num //= 2
        it += 1
    w_dict[i] = temp_direction

# 서, 북, 동, 남 : 1, 2, 4, 8
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]

# 방 구조 파악
def bfs():
    visited = [[False for _ in range(N)] for _ in range(M)]
    cnt = 0
    size = 0
    temp = []
    regime = [[0 for _ in range(N)] for _ in range(M)]
    idx = 1
    for i in range(M):
        for j in range(N):
            q = [[i, j]]
            if not visited[i][j] :
                visited[i][j] = True
                cnt += 1
                size = 1
                while q :
                    x, y = q[0]
                    regime[x][y] = idx
                    del q[0]
                    for d in range(4):
                        nx = x + dx[d]
                        ny = y + dy[d]
                        direction = d
                        if 0 <= nx < M and 0 <= ny < N and not visited[nx][ny] :
                            # Wall? 내가 향하고자 하는 방향에 벽이 있는지 확인하고 움직이자
                            # 벽 방향 동쪽 = 내 방향 서쪽 / 벽 방향 북쪽 = 내 방향 남쪽
                            wall = w_info[nx][ny]
                            if w_dict[wall][(direction + 2) % 4] != 1 :
                                visited[nx][ny] = True
                                size += 1
                                regime[nx][ny] = idx
                                q.append([nx, ny])
                temp.append(size)
                idx += 1
            else :
                continue
    adj = []
    for i in range(M): # 행 기준
        # 붙어 있는 방 정보 확인
        num_of_room = regime[i][0]
        for j in range(1, N):
            if num_of_room != regime[i][j] :
                if [num_of_room, regime[i][j]]  not in adj and [regime[i][j], num_of_room] not in adj:
                    adj.append([num_of_room, regime[i][j]])
                num_of_room = regime[i][j]
    for j in range(N):
        num_of_room = regime[0][j]
        for i in range(1, M):
            if num_of_room != regime[i][j] :
                if [num_of_room, regime[i][j]] not in adj and [regime[i][j], num_of_room] not in adj:
                    adj.append([num_of_room, regime[i][j]])
                num_of_room = regime[i][j]
    maxValue = 0
    for i, j in adj :
        size = temp[i-1] + temp[j-1]
        maxValue = max(maxValue, size)
    return cnt, max(temp), maxValue

result = bfs()
for i in range(len(result)):
    print(result[i])