[백준] 2234 성곽 python

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

2234번: 성곽

그래프 탐색 문제이다. 

문제를 풀기 전 다음 순서로 구현하려고 했다.

1. 입력

우선 방 개수와 크기를 알아야하므로 방의 개수를 저장하는 변수(num_room)와 각 방 크기를 저장하는 리스트(room_size)를 만들었다. 그리고 visit 배열을 만들어서 방문한 점인지 파악했다.

2. 그래프(이차원 배열) 탐색

2-1. 방 개수와 크기 확인

모든 자리를 순회하면서 BFS를 진행했다. 방문한 점이 아니면 새로운 방이므로 해당 점을 기준으로 그래프 탐색을 진행했다. bitmask를 사용해서 벽이 있는지 확인할수 있었고 벽이 없을 때 큐에 값을 추가했다. 탐색이 끝나면 저장한 방크기를 리턴했고, 메인 함수에 방크기를 저장하는 배열이 있어서 리턴받은 값을 추가했다.

3. 인접 그래프 생성 및 방 합친 크기 탐색

그다음 visit 배열을 사용해서 인접 그래프를 생성했다. 모든 지점을 순회하면서 인접한 칸의 방 번호가 다르면 그래프(adj_list)에 추가했다. 인접 그래프를 다 만들면 인접한 점(room_size[i], room_size[adj_list[i][j]])끼리의 크기를 더해서 가장 큰 값을 파악했다.

4. 답 출력

num_room, sum(room_size), max_c_size

 

하지만 이렇게 진행하다보니 인접 그래프를 다시 순회하면서 만들어야해서 오래 걸릴것 같았다. 그래서 BFS 를 진행할 때 인접 그래프(adj_list)도 같이 생성했다. 벽이 있을 때 인접한 방인지 체크해서 인접 그래프를 만들수 있었다. 

if visit[nr][nc] and visit[nr][nc] != num_room:
    # make graph
    adj_list[num_room].add(visit[nr][nc])
    adj_list[visit[nr][nc]].add(num_room)

위의 방식으로 인접한 방인지 체크를 했다. 인접한 점이 방문하지 않은 점이면 방의 번호를 알수 없으므로 넘어가고, 방문한 점인 경우 방 번호가 있으므로, 현재 확인하고 있는 방의 번호와 다를 때 인접 리스트에 추가했다. 각각의 리스트에 추가를 하는 이유는 방 번호가 클 때만 방 번호가 작은 것과 인접한 것을 확인할수 있기 때문이다. 그리고 값들이 중복 될 것이므로 set을 사용해서 진행했다.

 

 

# import sys; input = sys.stdin.readline
from collections import deque

d = [(0, -1), (-1, 0), (0, 1), (1, 0)]  # west/north/east/south
def bfs(sr, sc):
    global N, M, castle, visit, num_room, adj_list
    q = deque()
    q.append((sr, sc))
    size = 0
    adj_list.append(set())
    while q:
        r, c = q.popleft()
        if visit[r][c]: continue
        size += 1
        visit[r][c] = num_room
        for i in range(4):
            nr, nc = r + d[i][0], c + d[i][1]
            if 0 > nr or nr >= M or 0 > nc or nc >= N:
                continue
            if castle[r][c] & (1 << i):
                # if bit value is 1, there is a wall
                if visit[nr][nc] and visit[nr][nc] != num_room:
                    # make graph
                    adj_list[num_room].add(visit[nr][nc])
                    adj_list[visit[nr][nc]].add(num_room)
                continue
            q.append((nr, nc))
        
    return size


def main():
    global N, M, castle, visit, num_room, adj_list
    N, M = map(int, input().split())
    castle = [list(map(int, input().split())) for _ in range(M)]
    visit = [[0 for _ in range(N)] for _ in range(M)]
    num_room = 0
    room_size = [0]
    adj_list = [set()]
    # find maximum size, and a number of rooms
    for i in range(M):
        for j in range(N):
            if visit[i][j]: continue
            num_room += 1
            room_size.append(bfs(i, j))
    max_size = max(room_size)

    # find maximum size about combining two rooms
    max_c_size = 0
    select = [0 for _ in range(num_room + 1)]
    for i in range(1, num_room + 1):
        select[i] = 1
        for adj in adj_list[i]:
            if select[adj]: continue
            max_c_size = max(max_c_size, room_size[i]+room_size[adj])

    # output
    print(num_room, max_size, max_c_size, sep='\n')

if __name__ == "__main__":
    main()

 

난이도는 그렇게 어렵진 않았고, 벽 하나를 제거해서 방크기를 넓히는 것을 생각하는게 조금 오래걸렸다.