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

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

알고리즘

좌측상단에서 우측하단까지의 길을 찾는 문제이다. 

2차원인 배열을 1차원으로 바꾸어 그래프에 적용하였다. 현재 위치가 1인 상태에서 오른쪽이 1이면 이동가능이므로 그래프에 추가, 아래가 1이면 이동가능이므로 그래프에 추가한 뒤에 dfs를 실행한다.마지막 위치의 visited배열을 검사하여 True면 이동이 가능하므로 Yes를 출력해준다.dfs로 해결했지만, dp로도 풀 수 있는 문제인 것 같다.

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

n,m = map(int,input().split())
graph = [[] for _ in range(n*m)]
arr = []
for _ in range(m):
    arr.append(list(map(int,input().split())))

for i in range(m):
    for j in range(n):
        # right
        if j+1 <n:
            if arr[i][j] and arr[i][j+1]:
                graph[i*n+j].append(i*n+j+1)
        # down
        if i+1 <m:
            if arr[i][j] and arr[i+1][j]:
                graph[i*n+j].append((i+1)*n+j)

visited = [False]*(n*m)
dfs(graph, 0, visited)

if visited[n*m-1]:
    print("Yes")
else:
    print("No")