[BOJ] 2234. 성곽(Python) / BFS

2234번: 성곽

# 1시간 40분 소요

• 사용 알고리즘 : BFS 너비 우선 탐색
• 문제 푸는 흐름은 아래 코드에 주석으로 잘 적어놨고,
• makeBinInfo() 함수
  • binInfo 딕셔너리에 0~16 숫자를 4자리 이진수로 변환한 정보를 담아줬다.(0: 나갈 수 있음, 1: 벽. 나갈 수 없음)
• checkRooms() 함수
  • visited 배열에 방의 번호를 적으며 bfs를 퍼트렸다.
  • 이 때, 방 번호를 binInfo라는 딕셔너리를 활용해 현재 내 번호에 해당하는 남, 동, 북, 서 방향으로 벽인지, 나갈 수 있는 곳인지, 내가 이동할 곳에서 나를 받아줄 수 있는 곳인지 확인해 둘다 0(벽 없음)이라면 이동할 수 있는 곳으로 방 번호를 표시하고, 큐에 담는다.
  • roomInfo 딕셔너리에 (방 번호 : 방 넓이) 정보 저장
  • checkRooms함수 실행할 때마다 roomCnt + 1하고, 그 때의 넓이를 구해 최댓값 갱신하며 maxArea를 구함
• checkBoundary() 함수
  • bfs로 visited 배열을 참고해 다음 위치가 나와 같은 방이면 check 배열에 내 번호를 그리며 그대로 큐에 담고
  • 나와 다른 방의 번호를 가졌다면, roomInfo를 참고해 이동할 곳의 방의 넓이들 중 가장 큰 넓이를 가진 방의 넓이와 내 방의 넓이를 더해 리턴
• 연결된 두 방을 합쳐 만들 수 있는 가장 큰 넓이 realMaxArea를 출력

 

파이썬 코드는 다음과 같다.

---

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

# 남 동 북 서
dr = (1, 0, -1, 0)
dc = (0, 1, 0, -1)
rev = (2, 3, 0, 1)  # 방향 전환 - 북 서 남 동

def makeBinInfo():
    binInfo = dict()
    for num in range(16):
        binNum = bin(num)[2:]       # 10진수 => 이진수(문자열) 변환
        binInfo[num] = list(map(int, "0"*(4-len(binNum))+binNum))
    return binInfo

# bfs로 visited에 방 번호 표시
def checkRooms(sr, sc, cnt):
    area = 1
    visited[sr][sc] = cnt	# 방 번호 표시
    Q = deque([(sr, sc)])
    while Q:
        r, c = Q.popleft()
        num = A[r][c]
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            # 격자 밖 or 이미 방문
            if not (0 <= nr < R and 0 <= nc < C) or visited[nr][nc]:
                continue
            # 현 위치에서 나갈 수 있는 방향이고, 이동할 위치에서 현 위치에서 들어오는 곳이 뚫려있다면
            if not binInfo[num][d] and not binInfo[A[nr][nc]][rev[d]]:
                area += 1
                visited[nr][nc] = cnt
                Q.append((nr, nc))
    return area

# bfs로 경계선 방들 검사
def checkBoundary(sr, sc):
    boundarySet = set()     # 경계선 번호 검사 중복으로 하지 않기 위함
    num = visited[sr][sc]   # 현재 방 번호
    boundaryArea = 0        # 갱신용 넓이
    check[sr][sc] = num     # 방문 표시
    Q = deque([(sr, sc)])
    while Q:
        r, c = Q.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < R and 0 <= nc < C):
                continue
            if check[nr][nc] == num:    # 이미 방문했으면 
                continue
            if visited[nr][nc] == num:  # 나와 같은 방이면 그냥 방문 표시
                check[nr][nc] = num
                Q.append((nr, nc))
            else:   # 나와 다른 방이면 검사
                boundaryNum = visited[nr][nc]       # 경계에 있는 방 번호
                if boundaryNum not in boundarySet:  # 첫 검사인 경우
                    boundarySet.add(boundaryNum)
                    # 경계에 있는 방 크기를 갱신할 수 있다면 
                    if boundaryArea < roomInfo[boundaryNum]:
                        boundaryArea = roomInfo[boundaryNum]
    return roomInfo[num] + boundaryArea     # 원래 방 크기와 합친 크기

# main
C, R = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(R)]
binInfo = makeBinInfo()     # 0~16 숫자 이진수 표현 정보 딕셔너리

roomCnt, maxArea = 1, 0     # 방의 갯수, 가장 큰 방 구하기
roomInfo = dict()           # 방별 넓이 정보(경계 방들 크기와 합쳐 확인하기 위함)
visited = [[0] * C for _ in range(R)]
for sr in range(R):
    for sc in range(C):
        if not visited[sr][sc]:
            # 연결된 방 방문 표시, 방의 넓이 리턴
            area = checkRooms(sr, sc, roomCnt)
            maxArea = max(maxArea, area)
            roomInfo[roomCnt] = area
            roomCnt += 1

realMaxArea = 0     # 벽 뚫어 합쳤을 때의 최대 크기
check = [[0] * C for _ in range(R)]
for sr in range(R):
    for sc in range(C):
        if not check[sr][sc]:   # 첫 확인
            area = checkBoundary(sr, sc)   # bfs로 경계선 방과 합한 방 비교
            realMaxArea = max(realMaxArea, area)    # 최댓값 갱신

print(roomCnt-1)    # roomCnt 1부터 시작했기 때문에 -1 해줌
print(maxArea)            
print(realMaxArea)

---

• 시간 : 176ms / 메모리 : 126568kb
• 고찰 : 어려워 보였지만, 주어진 맵의 숫자 자체를 이진수로 변환해 4자리로 맞추니 생각보다 간단했다. 첫 번째, 두 번째 답 구하는 데 55분 정도 걸렸고, 남은 시간동안 어떻게 하면 벽을 뚫었을 때 최대 넓이를 구할 수 있을지 고민하며 코딩하는데 좀 시간이 걸렸다. 변수들이 많아서 헷갈리지 않게 정신을 집중하는 힘이 필요했다.. 한번에 pass를 받아 좋았다 ㅋㅋㅋ 난 재미있게 풀었다!^_^