1260

1260번 파이썬

bfs랑 dfs를 공부했던 블로그를 참고해서 했는데 정점과 간선을 이용한 그래프를 python의 dictionary를 이용하면 편리하게 정점 사이의 연결들을 관리할 수 있는 것 같다. dfs의 경우 stack의 pop과 정렬할 때 reverse 옵션을 true로 했는데 dfs가 깊이 탐색이다 보니 처음에 시작점으로 주어진 v에서 뻗쳐나갈 때 하나의 깊은 가지까지 다 뻗어나가고 나서야 다른 가지를 탐색하기 때문이다. 예를 들어 처음 입출력을 예로 들어 연결된 간선을 dic으로 표현하면 {1:[2,3,4],2:[1,4],3:[1,4],4:[1,2,3]}가 되는데 1번을 시작점으로 잡았을 경우 1(stack 배열이 reverse를 만나면서 [4,3,2]로 바뀜)->2( stack에서 2를 꺼내고 2랑 연결된 ..