0315. [BOJ#31575] 도시와 비트코인

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

31575번: 도시와 비트코인

1 초

512 MB

91

36

30

37.500%

문제

전날에 비해 비트코인의 시세가 백만원이나 오른 어느 아침, 진우는 거래소에 가서 비트코인을 매도하려고 한다. 현재 비트코인의 시세가 점점 떨어지고 있기 때문에 진우는 최대한 빨리 거래소에 가야 한다.

도시는 가로 �$N$, 세로 �$M$ 크기의 격자 모양으로 이루어졌다. 진우는 북서쪽 끝에 있고 거래소는 남동쪽 끝에 있다. 도시의 일부 구역은 공터 또는 도로라서 진우가 지나갈 수 있지만, 어떤 구역은 건물이 있어서 진우가 갈 수 없다.

진우는 최대한 빨리 거래소에 가야 하므로, 동쪽(오른쪽) 또는 남쪽(아래쪽)으로만 이동하여 거래소로 도착할 수 있어야 한다. 진우를 도와 거래소로 갈 수 있는지 구하는 프로그램을 작성하여라. 진우의 현재 위치가 거래소일 수 있다.

입력

첫 번째 줄에 도시의 가로 크기 �$N$과 세로 크기 �$M$ (1≤�,�≤300$1 \le N, M \le 300$)이 주어진다.

두 번째 줄부터 �$M$개의 줄에는 도시의 형태를 나타내는 �$N$개의 정수가 공백을 사이에 두고 주어진다. 각 칸이 1인 경우 진우가 갈 수 있는 칸을 의미하고 0인 경우 진우가 갈 수 없는 칸을 의미한다.

왼쪽 위의 끝 칸과 오른쪽 아래의 끝 칸은 모두 1이다.

출력

첫 번째 줄에 진우가 거래소로 갈 수 있으면 Yes를, 그렇지 않으면 No를 출력한다.

---

 

제출 코드

di = [0, 1] # 오른쪽 아래쪽
dj = [1, 0]

def dfs(si, sj):
    global result 
    
    if si == M-1 and sj == N-1:
        result = 'Yes'
        return
        
    
    for k in range(2):
        ni = si + di[k]
        nj = sj + dj[k]

        if 0 <= ni < M and 0 <= nj < N and not visited[ni][nj] and arr[ni][nj] != 0:
            visited[ni][nj] = True
            dfs(ni, nj)            
        
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(M)]
visited = [[False] * N for _ in range(M)]
visited[0][0]=True
result = 'No'
dfs(0,0)
print(result)

문제의 주인공이 익숙한 이름이라 재밌었던 문제~

이정도 난이도의 그래프문제는 빠르게 매도가능이다..!