BAEKJOON 1260 : DFS와 BFS

기본적인 dfs와 bfs 문제다.

기본이라서 무난하게 풀었지만, 그래도 삽질을 조금 했다.^^(삽질의 내용은 나중에 나온다ㅜ)

 

나는 이 문제를 풀기 위해 먼저 이어져 있는 노드를 다음과 같이 표로 표현해 봤다.

 

예를 들어,

 

4 5 1

1 2

1 3

1 4

2 4

3 4

 

이렇게 입력이 된다면 표로는 이렇게 나타낼 수 있는 것이다. 이렇게 시각화를 하면 훨씬 문제를 풀기가 수월해지는 것 같다.

	1	2	3	4
1	0	1	1	1
2	1	0	0	1
3	1	0	0	1
4	1	1	1	0

 

이렇게 해서 풀어낸 코드가 이것이다. python으로 코딩했다.

 

from collections import deque

n, m, v = map(int, input().split())
arr = [[0]*(n+1) for j in range(n+1)]

for i in range(m):
    x, y = map(int, input().split())
    arr[x][y] = 1
    arr[y][x] = 1

#dfs
visited = [0]*(n+1)

def dfs(input):
    print(input, end = ' ')
    visited[input] = 1

    for i in range(1, n+1):
        if(arr[input][i] == 1 and visited[i] == 0):
            dfs(i)

dfs(v)

print()

#bfs
visited = [0]*(n+1)

def bfs(input):
    queue = deque()
    queue.append(input)
    visited[input] = 1

    while queue:
        x = queue.popleft()
        print(x, end = ' ')

        for i in range(1, n+1):
            if arr[x][i] == 1 and visited[i] == 0:
                visited[i] = 1
                queue.append(i)

bfs(v)

 

삽질은 bfs(v)라고 하면 될것을 위에서 dfs(v)라고 잘 하다가 갑자기 print(bfs(v))라고 한 것이다. 이런짓을 하니 bfs 탐색 끝에 None이 같이 출력되었다 ㅎㅎ....

정말 queue가 비었는데도 돌아가는 줄 알고 뻘짓했다! 그래도 금방 찾아내서 다행이다,,,ㅜ