[Python] 26076번 곰곰이의 식단 관리 2

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

---

 

25/09/12

 

 

0-1 BFS문제다. 이전에 곰곰컵에 나가서 틀린 이후에 한참동안 묵혀놨다가 해결해서 적어본다.

---

 

문제 접근 방식:

 

 

2025.09.15 - [알고리즘/백준 문제 풀이] - [Python] 3140번 GULIVER

[Python] 3140번 GULIVER

기본적인 접근 방식은 위의 문제와 매우매우매우 유사하다.

 

단지 해당 문제는 정답이 0, 1, 2로만 제한되어있다는 사실이다.

 

먼저, 시작점에서 그냥 BFS를 돌려서 도착점으로 갈 수 없다면 0을 출력하면 된다.

 

문제는 1과 2를 구분해야한다는 사실인데, 어떻게 하면 시작점과 도착점을 두 부분으로 "분리하도록" 벽을 세울 수 있을까?

 

위의 이전 문제에서는 위와 아래로 분리해야했기 때문에 왼쪽벽에서 시작해서 오른쪽 벽에 도달하면 종료되는 0-1 BFS를 수행했다.

 

이번에는 왼쪽 위 모서리와 오른쪽 아래 모서리가 분리되게끔 해야한다. 그렇다면?

 

왼쪽 위 모서리와 오른쪽 아래 모서리가 제외된 윗변과 오른쪽 변의 모든 점에서 시작해서 아랫변과 왼쪽 변으로 도착하는 0-1 BFS를 수행하면 된다.

 

해당 BFS를 수행하면 끝이다.

 

여담으로 대회 당시에는 이런 개념을 몰라서 많은 조건분기로 비비려했으나 실패했다.

 

또한 대각선으로 나누는 부분을 몰라서, 맨 처음 코드 짰을 때에는 위에서 시작해서 아래로 내려오는 0-1 BFS, 왼쪽에서 시작해서 오른쪽으로 가는 0-1BFS, 왼쪽에서 시작해서 위로 가는 0-1 BFS, 오른쪽에서 시작해서 아래로 내려가는 0-1BFS, 총 4번을 돌렸다.

 

사실 이렇게 해도 돌아가긴 하지만 오래 걸린다....

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 26076번 곰곰이의 식단 관리 2
# BFS
import sys
from collections import deque
input = sys.stdin.readline

def solve():
    N, M = map(int, input().rstrip().split())
    MAP = [list(map(int, input().rstrip().split())) for _ in range(N)]
    dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]

    queue = deque()
    queue.append((0, 0))
    visited = [[0 for _ in range(M)]
            for _ in range(N)]
    visited[0][0] = 1
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr, nc = r+dr[i], c+dc[i]
            if 0 <= nr < N and 0 <= nc < M and MAP[nr][nc] == 0 and visited[nr][nc] == 0:
                visited[nr][nc] = 1
                queue.append((nr, nc))
    if visited[N-1][M-1] == 0:
        print(0)
        return
    
    # [-] 오른쪽 위에서 왼쪽 아래로 내려오는 0-1 BFS
    min_time = 2000*2000
    ddr, ddc = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
    visited = [[0 for _ in range(M)] for _ in range(N)]
    queue = deque()
    for c in range(1, M):
        if MAP[0][c] == 1:
            queue.appendleft((0, c, 0))
            visited[0][c] = 1
        else:
            queue.append((0, c, 1))
            visited[0][c] = 1
    for r in range(1, N-1):
        if MAP[r][M-1] == 1:
            queue.appendleft((r, M-1, 0))
        else:
            queue.append((r, M-1, 1))
            
    while queue:
        r, c, time = queue.popleft()
        if (r == N-1 or c == 0) and (r, c) not in [(0, 0), (N-1, M-1)]:
            min_time = min(min_time, time)
            break
        for i in range(8):
            nr, nc = r+ddr[i], c+ddc[i]
            if 0 <= nr < N and 0 <= nc < M and visited[nr][nc] == 0:
                visited[nr][nc] = 1
                if MAP[nr][nc] == 1:
                    queue.appendleft((nr, nc, time))
                else:
                    queue.append((nr, nc, time+1))
    if min_time >= 2:
        print(2)
    else:
        print(1)


solve()