[BOJ] 도시와 비트코인 - 31575 (S3)

시간 제한	메모리 제한
2 초	1024 MB

문제

N×M 크기의 도시가 있다. 도시의 각 칸은 비트코인을 받을 수 있는 곳(1)이거나 받을 수 없는 곳(0)이다.

현재 (0, 0) 위치에 있고, (M-1, N-1) 위치로 이동하려고 한다. 이동할 때는 오른쪽이나 아래로만 이동할 수 있다.

비트코인을 받을 수 있는 칸으로만 이동하여 목적지까지 갈 수 있는지 판단하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 100)

둘째 줄부터 M개의 줄에 도시의 정보가 주어진다. 각 줄에는 N개의 정수가 주어지며, 0 또는 1이다.

출력

(0, 0)에서 (M-1, N-1)까지 갈 수 있으면 “Yes”를, 없으면 “No”를 출력한다.

풀이

이 문제는 격자 그래프에서 경로 존재 여부를 판단하는 문제이다. BFS, DFS, DP 등 여러 방법으로 해결할 수 있다.

접근 방법

BFS를 이용한 풀이

시작점에서 BFS를 수행하며 오른쪽과 아래로만 이동한다. 목적지에 도달하면 “Yes”, 도달하지 못하면 “No”를 출력한다.

핵심 아이디어

1. (0, 0)에서 시작
2. 오른쪽(→), 아래(↓) 방향으로만 이동
3. 값이 1인 칸만 이동 가능
4. (M-1, N-1)에 도달하면 성공

코드

from collections import deque

N, M = map(int, input().split())

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

dyx = ((1, 0), (0, 1))

q = deque([(0, 0)])
visited = set([(0, 0)])

is_possible = False

if N == 1 and M == 1:
    is_possible = True

while q:
    y, x = q.popleft()
    for dy, dx in dyx:
        ny, nx = y + dy, x + dx
        if not(0 <= ny < M and 0 <= nx < N):
            continue
        if space[ny][nx] == 0:
            continue
        if (ny, nx) in visited:
            continue
        if (ny, nx) == (M - 1, N - 1):
            is_possible = True
            break

        q.append((ny, nx))
        visited.add((ny, nx))
    else:
        continue
    break

# print(visited)
print('Yes' if is_possible else 'No')

코드 설명

초기화

N, M = map(int, input().split())
space = [list(map(int, input().split())) for _ in range(M)]

dyx = ((1, 0), (0, 1))

• N: 가로 크기, M: 세로 크기
• dyx: 아래(↓), 오른쪽(→) 이동 방향

예외 처리

if N == 1 and M == 1:
    is_possible = True

• 1×1 크기일 때는 이미 목적지에 있음

BFS 탐색

while q:
    y, x = q.popleft()
    for dy, dx in dyx:
        ny, nx = y + dy, x + dx
        if not(0 <= ny < M and 0 <= nx < N):
            continue
        if space[ny][nx] == 0:
            continue
        if (ny, nx) in visited:
            continue
        if (ny, nx) == (M - 1, N - 1):
            is_possible = True
            break

        q.append((ny, nx))
        visited.add((ny, nx))

• 범위 체크
• 비트코인을 받을 수 없는 칸(0) 제외
• 방문 체크
• 목적지 도달 확인
• 큐에 추가 및 방문 처리

조기 종료

    else:
        continue
    break

• 목적지에 도달하면 즉시 종료

시간 복잡도

• BFS: O(N × M)
• 각 칸을 최대 한 번씩 방문
• N, M ≤ 100이므로 최대 10,000번의 연산

DP를 이용한 풀이

동적 계획법으로도 해결할 수 있다:

N, M = map(int, input().split())
space = [list(map(int, input().split())) for _ in range(M)]

# dp[y][x]: (0,0)에서 (y,x)까지 갈 수 있는지
dp = [[False] * N for _ in range(M)]
dp[0][0] = (space[0][0] == 1)

for y in range(M):
    for x in range(N):
        if space[y][x] == 0:
            continue
        if y > 0 and dp[y-1][x]:
            dp[y][x] = True
        if x > 0 and dp[y][x-1]:
            dp[y][x] = True

print('Yes' if dp[M-1][N-1] else 'No')

DP 방식:

• dp[y][x]: (0,0)에서 (y,x)까지 도달 가능 여부
• 위에서 오거나 왼쪽에서 올 수 있으면 도달 가능
• 공간 복잡도: O(N × M)

주의 사항

1. 좌표계: 입력은 행(M) × 열(N) 순서
2. 시작/끝점: (0, 0)에서 (M-1, N-1)까지
3. 이동 방향: 오른쪽과 아래로만 이동 가능
4. 1×1 예외: 시작점이 곧 도착점인 경우 처리

다른 접근

DFS로도 해결 가능하지만, 이 문제는 최단 경로를 구하는 것이 아니라 경로 존재 여부만 확인하면 되므로 BFS나 DP가 더 효율적이다.