[BAEKJOON] 1260 DFS와 BFS
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
예제 입력 1 복사
4 5 1
1 2
1 3
1 4
2 4
3 4
예제 출력 1 복사
1 2 4 3
1 2 3 4
예제 입력 2 복사
5 5 3
5 4
5 2
1 2
3 4
3 1
예제 출력 2 복사
3 1 2 5 4
3 1 4 2 5
예제 입력 3 복사
1000 1 1000
999 1000
예제 출력 3 복사
1000 999
1000 999
이 문제는 dfs, bfs 기본 문제.
dfs와 bfs를 이해하기 좋은 문제이다.
이걸 제일 먼저 풀걸,,,
거저 주는 문제였네...
dfs와 bfs의 차이는 말 그대로 재귀 + 스택이냐
큐 사용이냐 차이이다.
많이 안풀어봐서 장담은 못하겠지만 아마도.
그래서 문제가 요구하는 것처럼 탐색 정점 출력하게 구현하였다.
그리고 입력 받은 그래프를 넣을 배열 생성
주석한 것과 안한 것은 똑같이 동작하는 코드인데
개인적으로 주석한게 나는 직관적이여서 편하긴 한데
최대한 1줄로 쓸 수 있게 밑에 코드를 익숙해지려고 작성하는 중...
그리고 이 문제 같은 경우 처음에 작성된 코드는 위와 같았다.
근데 알고보니 실수를 2개나 해버린 것...
첫번째는 이 문제는 정점 값이 작은 곳부터 방문한다는 것.
* 문제를 잘 읽자...
그리고 두번 째는 입력으로 주어지는 간선은 양방향이라는 것...
* 문제를 잘 읽자... 2222
그래서 양방향으로 추가를 하였고 작은 정점부터 접근해야되기 때문에
정렬을 해주었다
.