문제 링크
https://softeer.ai/practice/6246
🕒 Python 풀이시간: 30분
from collections import deque
n,m=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]
dx=[0,0,-1,1]
dy=[-1,1,0,0]
def dfs(now,path,point):
global endPoint,answer,board
if now==endPoint and len(point)==0:
answer+=1
return
for i in range(4):
nx=now[0]+dx[i]
ny=now[1]+dy[i]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
if board[nx][ny]==1:
continue
if (nx,ny) in path:
continue
path.append((nx,ny))
tmp=-1
if len(point)>0 and point[0]==(nx,ny):
tmp=point.popleft()
dfs((nx,ny),path,point)
if tmp!=-1:
point.appendleft(tmp)
path.pop()
arr=list(map(int,input().split()))
startPoint=(arr[0]-1,arr[1]-1)
point=deque()
for _ in range(m-2):
x,y=map(int,input().split())
point.append((x-1,y-1))
arr=list(map(int,input().split()))
endPoint=(arr[0]-1,arr[1]-1)
answer=0
path=[startPoint]
dfs(startPoint,path,point)
print(answer)순서대로 방문하는 경로 찾기: 모든 경우의 수를 세라! 🚶♂️🔍
주어진 지점을 주어진 지점을 순서대로 방문하는 모든 방법의 갯수를 찾으면 된다. 이 때, 방문한 지점은 방문할 수 없다. 그렇기 때문에 시작지점에서 부터 DFS를 진행하면서 방문해야 하는 지점을 큐에 넣어놓고 맨 앞에 지점이 현재 지점과 일치하면 뺀다. 이렇게 하면 순서대로 방문하는지가 마지막 경우에 체크될 수 있다. 만약에 가야하는 지점을 전부가지 못하거나 순서를 지키지 않았다면 큐에 원소가 남게 된다. 그렇기에 이 방법을 통해 주어진 지점을 순서대로 방문하는 모든 경우를 찾을 수 있다.
이렇게 Python으로 Softeer의 "순서대로 방문하기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
