[백준 실버2] 1260 DFS와 BFS.py

<문제 설명>

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제이다.

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.

 

입출력의 예는 다음과 같다.

예제 입력 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는 큐로 해결하려고 했다. 우선 입력 받은 데이터를 기준으로 그래프를 구성하기 위해 Graph set을 이용해서 그래프를 구성했다. 

이후 DFS, BFS 모두 방문한 노드를 넣기 위한 빈 리스트(visited = [])를 정의하고, dfs는 스택(역순 정렬)으로, bfs는 큐(순 정렬)로 노드를 하나씩 방문해나간다.

방문한 순서대로 visited에 들어가기 때문에 최종적으로 해당 리스트를 출력하면 된다.

 

<문제 풀이 코드>

#dfs = stack
#bfs = queue
#재귀보다는 이렇게 구현하자

n, m, v = map(int, input().split())
#map은 리스트의 요소를 지정된 함수로 처리해줌/새 리스트를 만듬?
#n, m, v에 각각 처음 input을 split한 값을 순서대로 int 형태로 넣어줌
#map을 사용하면 한번에 형지정, 변수 할당이 가능함

#정석의 그래프 만드는 것은 아래와 같다(연결 리스트 만들기)

'''
#만약 n개만큼의 정점이 존재하고, m개만큼의 입력을 받는다면 
graph = [[] for _ in range(n+1)] # n+1개만큼의 공간을 만들어서 graph[n]이 n번 정점을 나타내도록 해 준다 
for _ in range(m):
	x,y = map(int,input().split()) #만약 1 2를 입력받으면 
    graph[x].append(y) # 1번 정점에 2를 넣어주고 -> graph[1] = [2] 
    graph[y].append(x) # 2번 정점에 1을 넣어준다 -> graph[2] = [1]
'''

#Graph set 중복 거르고 교집합 구하기 쉽게 set 사용(위 기본식에서 약간 변형)
graph_list = [set([]) for _ in range(n+1)]

for _ in range(m):
    i, j = map(int, input().split())
    graph_list[i].add(j)
    graph_list[j].add(i)

#DFS
def dfs(graph_list, start):
    visited = []
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack += sorted(list(graph_list[node] - set(visited)), reverse = True)
            #스택은 뒤에서 나가니 역순 정렬
    return visited

#BFS
def bfs(graph_list, start):
    visited = []
    queue = [start]
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            queue += sorted(list(graph_list[node] - set(visited)))
            #큐는 앞부터 나가니 순정렬
    return visited

for i in list(dfs(graph_list, v)):
    print(i, end=" ")
print()
for j in list(bfs(graph_list, v)):
    print(j, end=" ")

채점 결과