BOJ 2636 치즈

링크: https://www.acmicpc.net/problem/2636

템플릿

time = 0
last_melt = 0

while True:
    melt_list = BFS_외부공기(board)

    if melt_list 비어있음:
        print(time)
        print(last_melt)
        break

    last_melt = len(melt_list)
    치즈를 0으로 변경(board)

    time += 1
    
  BFS 함수 규칙
queue ← (0,0)
visited[][] 초기화

while queue:
    현재 위치가 0(공기)이면 계속 확산
    주변이 1(치즈)이면 melt_list에 저장 (방문만 체크)

정답 코드

from collections import deque

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

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

def bfs_air():
    """외부 공기(0)가 퍼지는 영역을 BFS로 체크하고,
    그 과정에서 치즈(1)와 맞닿은 부분을 찾아 녹일 후보에 저장"""
    visited = [[False] * m for _ in range(n)]
    q = deque()
    q.append((0, 0))
    visited[0][0] = True

    melt = []  # 이번 턴에 녹을 치즈 좌표들

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

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

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                visited[nx][ny] = True

                if board[nx][ny] == 0:
                    q.append((nx, ny))
                elif board[nx][ny] == 1:
                    melt.append((nx, ny))

    return melt


time = 0          # 총 걸린 시간
last_melt = 0     # 마지막에 녹은 치즈 개수

while True:
    melt_list = bfs_air()

    if not melt_list:
        # 더 이상 녹을 치즈가 없다 → 종료
        print(time)
        print(last_melt)
        break

    # melt_list의 치즈들을 녹인다
    last_melt = len(melt_list)
    for x, y in melt_list:
        board[x][y] = 0

    time += 1

BOJ 3184 양

링크: https://www.acmicpc.net/problem/3184

핵심 요약

• 맵은 울타리(#)로 여러 "영역"으로 나눔
• 각 영역을 BFS/DFS로 한 번씩 탐색
• 영역 내부에서 o와 v 개수를 셈
• 규칙:
  - o > v → 양만
  - v >= o → 늑대만
  - 살아남은 값들을 최종 더하기

양 문제 BFS 구조

전체 양 수 = 0
전체 늑대 수 = 0

모든 칸 순회:
    만약 방문 안 했고, 벽(#)이 아니면 → BFS 시작

BFS에서 현재 영역의 양/늑대 수 세기:
    큐 돌면서 o → 양++, v → 늑대++
    인접 4방향 탐색 (범위, 방문 체크, 벽 제외)

한 영역 BFS가 끝나면:
    if 양 > 늑대:
        모든 양 누적
    else:
        모든 늑대 누적

정답 코드

from collections import deque

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

r, c = map(int, input().split())

# 맵 입력
map_lst = [list(input().strip()) for _ in range(r)]
visited = [[False]*c for _ in range(r)]

def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = True

    sheep = 0
    wolf = 0

    # 현재 위치에 양/늑대가 있는지 체크
    if map_lst[x][y] == 'o':
        sheep += 1
    elif map_lst[x][y] == 'v':
        wolf += 1

    while queue:
        cx, cy = queue.popleft()

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]

            if 0 <= nx < r and 0 <= ny < c:
                # 벽은 통과 불가
                if map_lst[nx][ny] != '#' and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))

                    if map_lst[nx][ny] == 'o':
                        sheep += 1
                    elif map_lst[nx][ny] == 'v':
                        wolf += 1

    # 한 영역 끝난 후 생존 판정
    return sheep, wolf


total_sheep = 0
total_wolf = 0

# 전체 탐색
for i in range(r):
    for j in range(c):
        if not visited[i][j] and map_lst[i][j] != '#':
            s, w = bfs(i, j)

            if s > w:
                total_sheep += s
            else:
                total_wolf += w

print(total_sheep, total_wolf)

BOJ 2468 안전 영역

링크: https://www.acmicpc.net/problem/2468

핵심 요약

• 비의 높이(h)를 기준으로
• 물에 잠기지 않는 영역(높이 > h) 을 BFS/DFS로 탐색해서
• 각 h에 대해 안전 영역이 몇 개인지 구하고
• 그중 최댓값을 출력하는 문제

체크 포인트

• h 값이 바뀔 때마다 맵 전체 BFS를 반복해야 함
• 높이 ≤ h 는 물에 잠김 → 이동 불가
• 높이 > h 는 안전 지대 → BFS로 연결된 칸을 묶음
• 영역 수를 누적하고, 최댓값을 갱신

정답 코드

from collections import deque

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

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

max_height = max(map(max, graph))

def bfs(x, y, height, visited):
    q = deque()
    q.append((x, y))
    visited[x][y] = True

    while q:
        cx, cy = q.popleft()
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                # 물에 잠기지 않고 아직 방문하지 않은 지역만 이동
                if not visited[nx][ny] and graph[nx][ny] > height:
                    visited[nx][ny] = True
                    q.append((nx, ny))


answer = 1  # 아무 지역도 잠기지 않는 경우(비가 안 옴)

for h in range(1, max_height + 1):
    visited = [[False] * n for _ in range(n)]
    safe_count = 0

    for i in range(n):
        for j in range(n):
            # h보다 큰 지역(= 물에 잠기지 않음)이고 방문 안 했으면 BFS 시작
            if graph[i][j] > h and not visited[i][j]:
                bfs(i, j, h, visited)
                safe_count += 1

    answer = max(answer, safe_count)

print(answer)

BOJ 1926 그림