문제

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

문제 이해

노드와 간선, 시작 노드 값을 받고 단순히 그 시작 노드부터 DFS와 BFS를 이용하면 풀 수 있는 문제이다. DFS는 지금까지 꽤 연습을 해서 오류없이 한번에 금방 구현을 했지만, BFS는 아직 서툴러서 그런지 몇번의 오류가 있었지만 구현을 했다.

각각 answer 리스트를 만들었고, 마지막에 각각의 리스트를 출력했다.

코드

# 1260번 DFS와 BFS

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

from collections import deque

def DFS(idx):
    global graph, answer_dfs, visited
    visited[idx] = True
    # 인덱스 순서대로 추가
    answer_dfs.append(idx)

    for i in range(1, N+1):
        if not visited[i] and graph[idx][i]:
            DFS(i)

def BFS(idx):
    global graph, answer_bfs, visited

    queue = deque()
    queue.append(idx)
    visited[idx] = True

    while queue:

        number = queue.popleft()
        answer_bfs.append(number)

        for i in range(N+1):
            if not visited[i] and graph[number][i]:
                visited[i] = True
                queue.append(i)
        


# 0. 입력 및 초기화
N, M, V = map(int, input().split())
visited = [False] * (N+1)
answer_dfs = []
answer_bfs = []

# 1. 연결 정보 입력
graph = [[0] * (N+1) for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

# 2. DFS/BFS 호출
DFS(V) #idx

# BFS에서 사용하기 위해 다시 False로 초기화
for i in range(N+1):
    visited[i] = False

BFS(V)

# 3. 출력

# '중간에 넣을 값'.join(string)이다. 이거 문자열 기준이므로
# map함수로 문자열로 만들어준다.
print(' '.join(map(str, answer_dfs)))
print(' '.join(map(str, answer_bfs)))

필요한 스킬셋 and 지식

''.join(문자열 리스트)

DFS/BFS 구현보다는 리스트의 값을 공백으로 나눠서 출력하는 것을 못해서 서칭을 했다. join함수는 앞의 따옴표 안에 있는 것을 기준으로 구분해서 문자열 리스트의 값을 합쳐준다. 따옴표안에 값을 안넣으면 그냥 붙여지고, 공백을 넣으면 공백을 기준으로 합쳐준다. 이번 문제에서는 공백을 기준으로 합치기 때문에 따옴표 안에 공백을 넣어준고, 정수형 리스트이기 때문에 map함수로 문자열로 바꾸어준다.

# '중간에 넣을 값'.join(string)이다. 이거 문자열 기준이므로
# map함수로 문자열로 만들어준다.
print(' '.join(map(str, answer_dfs)))
print(' '.join(map(str, answer_bfs)))