백준 성곽 2234번 Python 파이썬 풀이

이번 포스팅에서는 백준 성곽 2234번 문제를 python으로 푼 정답 코드를 작성해보려고 합니다. 각각 주석으로 달아놓았고 밑에는 간략하게 해설을 작성하였습니다.

 

 

백준 성곽 2234번 Python 파이썬 정답 코드

# 성곽
# 복습 횟수:0, 01:30:00, 복습필요O
import sys
from collections import defaultdict
si = sys.stdin.readline

M, N = map(int, si().split())
graph = [list(map(int, si().split())) for _ in range(N)]
visited = [[0 for _ in range(M)] for __ in range(N)]

# 남 동 북 서
# graph 모양 치환
for i in range(N):
    for j in range(M):
        info = bin(graph[i][j])[2:] # 이진수로 변환하는 함수
        info = '0' * (4 - len(info)) + info # 자리수 맞춰주기
        graph[i][j] = list(map(int, info))

def getNewLocation(x, y, idx):
    # 남쪽
    if idx == 0:
        return x+1, y
    # 동쪽
    if idx == 1:
        return x, y+1
    # 북쪽
    if idx == 2:
        return x-1, y 
    # 서쪽
    if idx == 3:
        return x, y-1 

def changeDir(idx):
    if idx == 0:
        return 2
    if idx == 1:
        return 3
    if idx == 2:
        return 0
    if idx == 3:
        return 1
    
def dfs(x, y, check):
    visited[x][y] = check # 방문 처리

    target = graph[x][y]
    
    for idx in range(4):
        if target[idx] == 1: continue

        nx, ny = getNewLocation(x, y, idx)
        if not (0 <= nx < N and 0 <= ny < M): continue
        if visited[nx][ny] != 0: continue

        # 가려는 방향의 벽도 체크해야함
        next_target = graph[nx][ny]
        dir = changeDir(idx)
        if next_target[dir] == 1: continue

        dfs(nx, ny, check)

    return

check = 1
# 1. 방 나누기
for i in range(N):
    for j in range(M):
        if visited[i][j] != 0: continue

        dfs(i, j, check)
        check += 1

print(check - 1)
# 2. 가장 넓은 방의 넓이
room_size_dict = defaultdict(int)

for i in range(N):
    for j in range(M):
        val = visited[i][j]

        if val not in room_size_dict.keys():
            room_size_dict[val] = 1
        else:
            room_size_dict[val] += 1

print(max(room_size_dict.values()))

# 3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
maxi = max(room_size_dict.values())
diff_set = set()

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for x in range(N):
    for y in range(M):
        check = visited[x][y]

        for idx in range(4):
            nx, ny = x + dx[idx], y + dy[idx]

            if not (0 <= nx < N and 0 <= ny < M): continue

            if check != visited[nx][ny]:
                tmp = [check, visited[nx][ny]]
                tmp.sort()

                diff_set.add(tuple(tmp))
                
# 전체를 돌면서 합쳐지는 방 숫자를 가진 것의 총 개수 체크
for x, y in diff_set:
    tmp = 0
    for i in range(N):
        for j in range(M):
            if visited[i][j] == x or visited[i][j] == y:
                tmp += 1
    
    maxi = max(maxi, tmp)
print(maxi)

 

 

 

백준 성곽 2234번 Python 파이썬 해설

1. 문제에서 0부터 15까지의 범위가 있고 이에 대해 힌트로 이진수를 주었습니다. 따라서 bin()을 사용하여 이진수로 변환하고 자리수를 맞춰주었습니다.

 

2. 방의 개수를 구하는 것이었으므로 dfs()나 bfs()를 활용해 visited로 체크해가면서 방을 구분하였습니다. 이때 주의할 점은 가려는 방향의 방 상태도 추가로 확인해주어야 하는 것이었습니다. 예를 들어 남쪽으로 가는 경우, 남쪽에 있는 방은 북쪽에 벽이 없어야 합니다. 이를 구현하기 위해 changeDir()의 메서드를 만들었습니다.

 

3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구하기 위해 각 위치마다 상하좌우를 체크하면서 값이 다른 경우 set에 넣었습니다. 이후 그 지점들의 방의 번호를 기준으로 더해 구하였습니다.