[Algorithm🧬] 백준 5850 : Perimeter

문제
한글

BFS 틀린 풀이

처음에는 연결성분마다 첫번째 4고 하나씩 늘어갈때마다 +2 에 구멍이 있으면 -4 하면 되는거 아닌가? 라고 생각했는데,

ㅇㅇㅇㅇㅇ
ㅇ ㅇ
ㅇㅇㅇ

이렇게 생긴게 반례 16인데 위의 식으로 풀면 2 * 11 - 4 = 18

# 처음에 푼거..
import sys
from collections import deque

def BFS(i, j):
    global cnt
    q = deque()
    q.append((i, j))
    들판[i][j] = 0
    cnt = 1

    while q:
        x, y = q.popleft()

        for dx, dy in adj:
            nx = x + dx
            ny = y + dy

            if not 0 <= nx < 100:
                continue
            if not 0 <= ny < 100:
                continue

            if 들판[nx][ny] == 1:
                q.append((nx, ny))
                들판[nx][ny] = 0
                cnt += 1


readl = sys.stdin.readline

n = int(readl())
건초들 = [list(map(int, readl().split())) for _ in range(n)]

들판 = [[0] * 100 for _ in range(100)]
adj = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for x, y in 건초들:
    들판[y-1][x-1] = 1

hole_cnt = 0

for i in range(100):
    for j in range(100):
        hole = 1
        if 들판[i][j] == 0:
            for x, y in adj:
                nx = x + i
                ny = y + j

                if 0 <= nx < 100 and 0 <= ny < 100 and 들판[nx][ny] == 0:
                    hole = 0
            if hole == 1:
                들판[i][j] = -1
                hole_cnt += 1


둘레 = 0
cnt = 0
for i in range(100):
    for j in range(100):
        if 들판[i][j] == 1:
            BFS(i, j)
            둘레 += 2 * (cnt + 1)
            cnt = 0

둘레 -= 4 * hole_cnt

print(둘레)

다시 풀이...

https://aronglife.tistory.com/entry/AlgorithmDFSUSACO-2013Feb-둘레

도저히 모르겠어서 보고 시작. 건초를 중심으로 찾는게 아니라 빈 부분을 중심으로 찾는거였다...

근데 해당 블로그의 DFS 를 그대로 파이썬으로 옮겨보니까 RecursiveError 가 나서 같은 방법을 BFS 로 탐색했고,

하다보니까 안되는 케이스가 생겨서 padding 을 추가했다.

import sys
from collections import deque

def BFS(i, j):
    cnt = 0
    q = deque()
    q.append((i, j))
    들판[i][j] = 2

    while q:
        x, y = q.popleft()

        for dx, dy in adj:
            nx = x + dx
            ny = y + dy

            if not 0 <= nx < 102:
                continue
            if not 0 <= ny < 102:
                continue

            if 들판[nx][ny] == 0:
                q.append((nx, ny))
                들판[nx][ny] = 2 # 빈 곳을 탐색해야하니까 2로 표시.
            elif 들판[nx][ny] == 1:
                cnt += 1 # 주변에 건초가 있으면 1을 늘린다. (해당 뱡향으로 edge 가 생기는 것!)
                # hole 은 애초에 세어지지도 않음.
    return cnt


readl = sys.stdin.readline

n = int(readl())
# 맨 가장자리가 건초여도 edge 를 세어줘야하기 때문에 padding 추가
건초들 = [list(map(int, readl().split())) for _ in range(n)]

들판 = [[0] * 102 for _ in range(102)]
adj = [(-1, 0), (1, 0), (0, -1), (0, 1)]


for x, y in 건초들:
    들판[y][x] = 1

    # 건초가 있는 주변만 빈 자리를 따지면 됨.



print(BFS(0, 0))