[백준 - Python] 2234 - 성곽

0. 문제 링크

 

 

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

2234번: 성곽

---

1. 풀이 방법

 

 

각 구역을 그룹화 한 다음에 처리함  
또한 인접한 그룹 번호도 넣어서 최댓값을 찾음  
비트마스킹을 써서 벽의 위치를 파악함

cnt는 특정 구역의 블록 갯수이고, adj는 특정 구역의 인접한 구역의 인덱스를 넣어놓았음

check는 블럭의 그룹을 적어놓은 리스트임

 

참고로 한 구역에 블럭이 하나만 있는 경우를 대비해서, 시작과 동시에 블럭에 그룹 번호를 부여하였음

 

다만 더 좋은 방법이 있을거라 생각됨

---

2. 코드

 

 

import sys
from collections import deque


def sol():
    m, n = map(int, sys.stdin.readline().split())
    board = [[b for b in map(int, sys.stdin.readline().split())] for _ in range(n)]
    check = [[0] * m for _ in range(n)]
    dir = [1, 2, 4, 8]      # 서, 북, 동, 남, 성곽 체크
    dy, dx = [0, -1, 0, 1], [-1, 0, 1, 0]       # 서, 북, 동, 남

    grp = 1
    cnt = dict()        # 구역의 개수
    adj = dict()        # 인접한 구격의 그룹 번호

    dq = deque()
    for i in range(n):
        for j in range(m):
            if check[i][j] == 0:
                dq.append([i, j])
                check[i][j] = grp       # 그룹 번호
                cnt[grp] = 1
                while dq:
                    y, x = dq.popleft()
                    for idx in range(4):
                        ny, nx = y + dy[idx], x + dx[idx]
                        if 0 <= ny < n and 0 <= nx < m:
                            if not board[y][x] & dir[idx]:      # 벽이 아니라면
                                if check[ny][nx] == 0:
                                    check[ny][nx] = grp     # 그룹 번호 입력
                                    cnt[grp] += 1       # 그룹의 개수 추가
                                    dq.append([ny, nx])
                            else:       # 벽인 경우
                                if check[ny][nx] != 0 and grp != check[ny][nx]:     # 방문했었고, 그룹 번호를 추가하지 않았다면
                                    adj[grp] = adj.get(grp, set()) | set([check[ny][nx]])
                grp += 1

    maximum = -1
    for i in adj.keys():
        for j in adj[i]:
            temp = cnt[i] + cnt[j]      # 인접한 애들을 싹 돌면서 최댓값을 갱신함
            maximum = temp if temp > maximum else maximum

    print(max(cnt.keys()))
    print(max(cnt.values()))
    print(maximum)

    return

sol()

---

3. 마무리

 

 

시간은 적게 나오긴 했는데, 뭔가 마음에 드는 방법은 아님