백준 1260번 파이썬 문제풀이 : DFS와 BFS

백준 1260번 : DFS와 BFS 문제풀이 [파이썬] 

---

DFS와 BFS 알고리즘에 대한 설명은 아래 포스팅에 있습니다.

2022.12.24 - [백준 알고리즘] - [알고리즘] DFS & BFS 알고리즘(2) - DFS 알고리즘

[알고리즘] DFS & BFS 알고리즘(2) - DFS 알고리즘

2023.01.27 - [백준 알고리즘] - [알고리즘] DFS & BFS 알고리즘(3) - BFS 알고리즘

[알고리즘] DFS & BFS 알고리즘(3) - BFS 알고리즘

 

<문제>

 

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에 대한 개념은 배웠지만

코드로 직접 구현해보는건 처음이라서 굉장히 애먹었던 문제!

그래도 두 알고리즘을 한번에 적용해볼 수 있는 기회라 좋은 문제였다.

 

 

일단 가장 먼저 문제에서 요구한 입력값들을 받아주기 위해

map 함수를 사용해 코드를 작성했다. 

또 인접행렬을 0,1로 만드는 경우가 많던데 

나는 T/F가 익숙해서 True, False로 인접행렬을 구현했다. 

 

 

그 아래에는 주어진 간선 개수만큼 입력을 받아,

연결된 노드들의 값은 True 값으로 바꿔주었다. 

이렇게 그래프를 만들어놓고 코드 작성을 시작했다. 

 

 

방문 처리한 값들도 리스트 형식으로 표현할 거기때문에

미리 만들었다. 

 

 

DFS를 구현한 함수다. 

BFS에 비해서는 작성에 어려움이 크게 없었다. 

큐 자료구조를 사용하는 것도 아니고, 그냥 재귀함수로 다들

많이 푸는것같아서 재귀함수로 간단하게 표현했다. 

 

 

 

다음은 BFS로 구현한 함수다. 

deque를 처음 사용해봐서 처음에는 애먹었는데

다른 사람들의 코드 풀이를 참고하면서 그 감을 익혔다.

알고리즘은 이론적으로 배우는거랑 코드로 구현하는건 또 

다른 차원의 문제인 것 같아서 공부가 많이 필요함을 느꼈다.