[Python][백준 23741][DFS] 야바위 게임 - 컴도리돌이

23741번: 야바위 게임

---

풀이과정

멍청한 상원이.. 그거 하나 제대로 기억 못 해서

나를 이렇게 힘들게 하다니,, 🤦‍♂️🤦‍♂️

 

해당 문제는 DFS로 접근하였습니다.

아마도 BFS로 접근하여도 무리 없이 문제를 해결할 거예요

 

시작 시 공이 놓여있는 정점 번호(x)부터 시작하여서

연결된 다른 정점으로 이동해서

이동 횟수가 Y인 정점을 저장해주면 됩니다.

 

하지만 해당 정점으로 이동할 때

정점으로 이동할 때 이동 횟수가 똑같은 경우

중복 탐색을 방지하기 위해서

[현재 노드][방문 횟수]로 방문 표시를 해주었습니다.

 

1. n, m, x, y를 입력받는다.

 

2. 위에 언급한 것처럼

"visited"으로 중복 탐색 방지용으로 방문 표시를 하였다.

(노드의 개수 x 최대 방문 횟수)

 

3. 주어진 정점을 graph 함수에 연결시켜준다.

 

4. dfs 탐색

4-1) 현재 정점과 현재 이동 횟수를 방문 표시한다.

4-2) 이동 횟수가 y와 같을 경우 answer에 현재 정점을 삽입하고 반환해준다.

4-3) 연결된 노드를 탐색한다. 

 

5. answer의 크기가 1보다 클 경우 answer 출력

아닐 경우 -1 출력.

---

풀이과정

import sys; input = sys.stdin.readline
n,m,x,y = map(int,input().split())
graph,answer = [[] for _ in range(n+1)],set()
visited = [[False] * (y+1) for _ in range(n+1)]
for _ in range(m) :
  v1,v2 = map(int,input().split())
  graph[v1].append(v2)
  graph[v2].append(v1)

def dfs(cur,cnt) :
  visited[cur][cnt] = True
  if cnt == y :
    answer.add(cur) ; return
  else :
    for next in graph[cur] :
      if not visited[next][cnt+1] :
        dfs(next,cnt+1)
dfs(x,0)
if len(answer) > 1 :  print(*answer)
else : print(-1)