DFS_깊이우선탐색1(24479)

문제

풀이

1. 1번 노드를 처음 시작하므로 첫번째 방문으로 visted 되었다고 표현하기 위해서 visted[1] 1로 바꿈

2. 1번 노드와 연결된 2번, 4번 중에 2번 노드가 더 작으므로 2번 노드 방문 -> 2번 노드 2번째로 방문하였으므로 visted[2] 2로 변경

3. 2번 노드와 연결된 1번,3번,4번 중 방문하지 않은 노드 중에 작은 값인 3번 노드 방문 -> 3번 노드 3번째로 방문하였으므로 visted[3] 3으로 변경

4. 4번 노드와 연결된 1번,3번,4번 노드 중 방문하지 않은 노드들이 없다.끝

그러면 5번 노드는 시작 노드 1번으로부터 방문하지 못하는 노드이므로 0으로 그냥 명시 ( 조건에서 방문 못하는 노드는 0이라고 명시하라고 하였으므로)

결론: 출력은 visted에 몇번째로 출력되는 지 출력되는 거다 !!!

※ 조심하기 ※ 출력되는 순서대로 출력하는 것이 아니라 몇번째로 출력되는지( dfs 하면서 출력하면 틀리는 이유)

풀이 방법

• n (정점의 수), m(간선의 수), r(시작 정점), graph( 연결 노드 그래프) , visted( 방문 순서 입력 그래프)

① 정점의 수(n),간선의 수(m),시작 정점(r) 입력 받기
② 간선의 수(m)만큼 입력 graph로 입력받은 후에 다 받고 난 후에 graph마다 하나씩 sort해서 오름차순으로 하게 하기
③ dfs 함수 선언하여서 dfs 할 때마다 visted에 cnt 값 부여하기 + dfs 실행 후에는 cnt값 1 증가해서 순차적으로 값 부여하기
④ visted 인덱스값이 0인 것은 보기 편하게 하기 위해서 한 것이므로 인덱스의 값이 0일 때 값 빼고 출력하기

코드

import sys
def input():
    return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 6)  
# sys.stdin=open("input.txt", "rt")
# 정점 수, 간선 수, 시작 정점

N, M, R = map(int,input().split())

# 연결 노드 그래프 초기화(1번 노드와 인덱스 값이 같게 하기 위해 n+1)
# [[],[],[],[],[],[]]
graph = [[]for _ in range(N+1)]

# 방문 순서 그래프(이것도 인덱스 값과 노드의 값이 동일하게 만들기 위해서 n+1)
visited = [0]*(N+1)

# 순차 입력
cnt = 1

for i in range(M): #연결된 노드 입력받기
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(N+1):# 오름차순 정리
    graph[i].sort()

def dfs(graph, v, visited):
    global cnt

    # 연결된 노드 방문
    visited[v]=cnt
    for i in graph[v]:
        if visited[i]==0: # 방문 안한 노드일경우
            cnt += 1
            dfs(graph, i, visited) # dfs 실행

dfs(graph,R,visited)

# 출력하기
for i in range(1,N+1):
    print(visited[i])