[Python] 백준_ 도시와 비트코인

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

📌 문제 탐색하기

가로N ,세로 M의 격자 모양으로 이루어진 도시에서 진우가 최대한 빠르게 거래소에 가야한다. 
도시의 일부 구역은 공터와 도로으로 이루어져 진우가 지나갈 수 있지만 특정 구역은 건물이 있어서 지나갈 수 없다.
진우는 최대한 빠르게 거래소에 가야 하므로 오른쪽(동쪽) 또는 아래쪽(남쪽)으로만 이동 가능하나다. 
해당 문제는 진우가 거래소로 갈 수 있는지 구하는 문제입니다. 

📌 가능한 시간복잡도

[멘토님 해설]
지도에서 정점은 최대 O(NM)개가 존재 가능하고 한 정점에서 최대 2개의 간선이 존재 가능함.
BFS/DFS 탐색은 한번 방문한 정점은 다시 방문하지 않는 다는 특징으로 가능한 시간복잡도는 O(NM) 이라고 합니다.

📌 코드 설계하기

- 입력값 N,M 입력받기
- BFS 탐색을 위한 초기값들을 설정하기
- 시작 지점부터 BFS 탐색 시작 
- 진우가 BFS 탐색 방식으로 남동쪽 끝에 도착했는지 확인하기

📌 정답 코드

import sys
# 1. 문제의 input을 받습니다.
n, m = map(int, sys.stdin.readline().split())
board = []
for _ in range(m):
    board.append(list(map(int, sys.stdin.readline().split())))

# 2. BFS 탐색을 위한 초기값들을 설정합니다.
visited = [[False] * n for _ in range(m)]
# 동쪽, 남쪽 탐색을 위한 방향 배열
dx = [0, 1]
dy = [1, 0]


# 3. BFS 탐색 함수를 구현합니다.
def bfs(x,y):
    queue = [(x, y)]
    visited[x][y] = True
    while queue:
        x, y = queue.pop()
        # 3-1. 현재 정점에서 동쪽, 남쪽으로 이동가능한지 탐색합니다.
        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 1 and not visited[nx][ny]: # 지도안에 존재하고, 공터/도로이면서 방문하지 않은 곳인지 확인합니다.
                visited[nx][ny] = True
                queue.append((nx, ny))


# 4. 시작 지점(북서쪽 끝)에서 BFS 탐색을 진행합니다.
bfs(0,0)
# 5. BFS 탐색 이후 남동쪽 끝에 방문이 가능했는지 확인합니다.
if visited[m-1][n-1]:
    print("Yes")
else:
    print("No")