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 모두 방문처리 후 다시 복구 시켜줌으로써 시간초과 및 답이 안나오는 문제가 발생했다...
방문 처리 복구를 지워주자 바로 통과 되었다.. 간단한 문제더라도 문제 조건을 계속 상기해야겠다..
'PS' 카테고리의 다른 글
[BOJ] Python 백준 해킹(10282) (0) | 2024.12.10 |
---|---|
[BOJ] Python 백준 가장 긴 바이토닉 부분 수열(11054) (1) | 2024.11.28 |
[BOJ] Python 백준 줄세우기(2631) (0) | 2024.11.28 |
[BOJ] Python 백준 상자넣기(1965) (0) | 2024.11.26 |
[BOJ] Python 백준 가장 큰 증가하는 부분 수열(11055) (0) | 2024.11.24 |
댓글