도시와 비트코인[백준 31575]

 

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

 

 

 

 일반적인 그래프 탐색 문제라서 bfs를 이용해서 해결했다. 

from collections import deque

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

directions = [(0, 1), (1, 0)]

def bfs():
    queue = deque([(0, 0)])  # 시작점
    visited = [[False] * n for _ in range(m)]  # 방문 여부
    visited[0][0] = True

    while queue:
        x, y = queue.popleft()
        if x == m - 1 and y == n - 1:
            return "Yes"

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

            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] == 1:
                visited[nx][ny] = True
                queue.append((nx, ny))
    return "No"




# 결과 출력
print(bfs())