[BOJ] 1260번 DFS와 BFS / 사용언어 : 파이썬(python)

※ 문제링크 

1260번: DFS와 BFS

※ 관련개념 및 참고사이트 

[Daily PS] 파이썬으로 구현하는 BFS와 DFS

해당 문제는 BFS와 DFS를 구현하는 문제였다. 문제를 풀기 전 개념에 대한 이해를 위해 구글링을 하던 중 설명이 잘 되어 있는 사이트가 있어서 해당 사이트를 참고하여 구현해보았다. 문제해결을 위해서는 먼저 입력값을 그래프 형태로 만들어주는 것이 필요해서 딕셔너리를 활용하여 그래프를 구현한 후 문제를 해결해보았다. 자세한 문제풀이 방법과 코드는 아래와 같다.

1. 입력 받은 값을 반복문과 딕셔너리를 활용하여 그래프형태로 구현한다.

2. 재귀함수를 이용하여 DFS와 BFS함수를 작성한다.

3. 입력받은 값들을 조건에 맞게 작성 후 출력한다.

+ 해당 문제에서는 간선이 양방향이라는 점, 간선이 이어지지 않았을 경우, 시작점을 출력해야한다는 점, 간선이 여러개면

작은 숫자부터 방문한다는 점을 반드시 유념하고 코드를 작성해야한다. 특히 런타임 오류는 간선이 이어지지 않은 경우에

대한 예외조건이 작성되지 않았을 경우 출력되는 경우가 많으며, 88%에서 틀린다면 간선이 이어지지 않았을 경우,

시작점을 출력하고 있는지를 확인해보면 좋다.

 

N, M, V = map(int, input().split())
dic = dict()
# 입력값을 딕셔너리로 그래프형태로 구현
for _ in range(M):
    key, value = map(int, input().split())
    if key not in dic:
        dic[key] = [value]
    else:
        dic[key].append(value)
    if value not in dic:
        dic[value] = [key]
    else:
        dic[value].append(key)

for key, value in dic.items():
    dic[key] = sorted(value)

# 방문한 곳을 확인하고 조건을 처리할 변수 생성(DFS)
visited1 = []
visited1.append(V)
def dfs(V):
    for line in dic[V]:
        if line in visited1:
            continue
        visited1.append(line)
        dfs(line)
    return

# 방문한 곳을 확인하고 조건을 처리할 변수 생성(BFS)
visited2 = []
visited2.append(V)
keys = []
keys.append(V)
def bfs(keys):
    if len(keys) == 0:
        return
    keys_p = keys[:]
    keys = []    
    for i in keys_p:
        for line in dic[i]:
            if line not in visited2:
                keys.append(line)
            if line in visited2:
                continue
            visited2.append(line)
    bfs(keys)

# 간선이 이어져 있지 않을 경우와 이어진 경우 출력문 작성
if V not in dic:
    print(V)
    print(V)
else:
    dfs(V)
    print(*visited1)
    bfs(keys)
    print(*visited2)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.