24479번 - 알고리즘 수업 - 깊이 우선 탐색 1
질문하기에 나와있는 반례들도 넣어서 실행시켜 보았는데 잘 나옵니다ㅠㅠ
제가 어떤 것을 놓치고 있는걸까요?.....
반례 찾아주시는 분은 복받으실꺼에요
예를 들어, 입력이 아래와 같이 주어진다고 가정하면
4 4 11 21 31 42 4
방문 순서는 1 -> 2 -> 4 -> 3가 되어야 하지만
질문자님의 코드는 stack에 push하면서 visit여부를 체크하므로 마치 bfs를 하듯이 1 -> 2 -> 3 -> 4 순서로 방문하게 됩니다.
(p.s 생각보다 반례 찾기 힘드네요 ㅎㅎ..)
좀 더 자세히 질문자님의 코드가 동작하는 방식을 설명하면 아래와 같습니다.
1. 1을 방문하면서 2, 3, 4를 stack에 push후 visited을 true로 바꿈
2. 2을 방문후 4를 방문해야 하는데 이미 1에서 4를 visited = true로 하였으므로 skip
3. 3을 방문
4. 4을 방문
stylecoke 님의 자세한 설명과 입력받는 방식 바꿔서(시간초과때문에ㅠㅠ) 해결했습니다 감사합니다!!ㅎㅎ
댓글을 작성하려면 로그인해야 합니다.
himinhee 1년 전
질문하기에 나와있는 반례들도 넣어서 실행시켜 보았는데 잘 나옵니다ㅠㅠ
제가 어떤 것을 놓치고 있는걸까요?.....
반례 찾아주시는 분은 복받으실꺼에요