[BOJ] Python 백준 침투(13565)

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

 

위 문제는 아래까지 도착이 가능한지를 확인하는 탐색 문제이다. 

해당 문제는 bfs, dfs로 모두 풀 수 있다.

dfs 방식

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

N,M = map(int,input().split())
s = [list(map(int,input().rstrip())) for _ in range(N)]
di = [1,-1,0,0]
dj = [0,0,1,-1]
def dfs(n,pi,pj):

    if pi == N-1 and s[pi][pj]==2:
        print("YES")
        exit()

    for i in range(4):
        ni,nj = pi + di[i], pj + dj[i]
        if 0 <= ni < N and 0 <= nj < M:
            if s[ni][nj] == 0:
                s[ni][nj] = 2
                dfs(n+1,ni,nj)


for j in range(M):
    if s[0][j] == 0:
        s[0][j] = 2
        dfs(0,0,j)


print("NO")

 

bfs 방식

import sys
from collections import deque
input = sys.stdin.readline

N,M = map(int,input().split())
s = [list(map(int,input().rstrip())) for _ in range(N)]
di = [1,-1,0,0]
dj = [0,0,1,-1]
def bfs(pi,pj):
    queue = deque()
    queue.append((pi,pj))
    s[pi][pj] = 2
    while queue:
        ci,cj = queue.popleft()
        if ci == N-1 and s[ci][cj] == 2:
            print("YES")
            exit()
        for i in range(4):
            ni,nj = ci+di[i], cj+dj[i]
            if 0 <= ni < N and 0 <= nj < M:
                if s[ni][nj] == 0:
                    s[ni][nj] = 2
                    queue.append((ni,nj))

for j in range(M):
    if s[0][j] == 0:
        bfs(0,j)


print("NO")

 

 

회고.

처음에는 백트래킹 방식으로 생각을 했었다. 하지만, 위 문제는 모든 경우의 수를 찾는 것이 아닌 하나의 경로만 끝점에 도달하면 종료하면 된다는 것을 생각하지 못했다...

bfs, dfs 모두 방문처리 후 다시 복구 시켜줌으로써 시간초과 및 답이 안나오는 문제가 발생했다...

방문 처리 복구를 지워주자 바로 통과 되었다.. 간단한 문제더라도 문제 조건을 계속 상기해야겠다..