백준 24479(깊이 우선 탐색 1) - Python(파이썬),Java(자바) - DFS

 

예제 문제 설명

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일 때 값 빼고 출력하기

Python (파이썬)

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 허용 깊이를 수동으로 늘려주는 코드
#정점의 수,간선의 수,시작 정점
n,m,r= map(int,sys.stdin.readline().split())
#연결노드 그래프 초기화(1번노드와 인덱스 값이 같게 하기 위해서 n+1로 )
#[[],[],[],[],[],[]]
graph=[[] for _ in range(n+1)]
#방문 순서 그래프 (이것도 인덱스 값과 노드의 값이 동일하게 만드릭 위해서 설정 )
visted =[0]*(n+1)
# 순차 입력
cnt=1
def dfs(graph,v,visted):
    #함수 밖에 cnt값을 쓰기 위해서 global이라고 명시
    global cnt
    #방문할 때마다 순차 값 변경
    visted[v]=cnt
    #연결된 노드 방문
    for i in graph[v]:
        #방문 안한 노드일 경우
        if visted[i]==0:
            #순차 증가
            cnt+=1
            #dfs 실행
            dfs(graph,i,visted)

#연결된 노드 입력 받기
for i in range(m):
    u,v = map(int,sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

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


dfs(graph,r,visted)
#순차 출력
for i in range(n+1):
    if i!=0:
        print(visted[i])

Java(자바)

import java.util.*;
import java.io.*;

public class Main {
    static int n,m,cnt;
    //몇번째 방문인지 
    public static int[] visted;
    //연결된 노드
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

	//dfs 
    public static void dfs(int x){
    	//순차 정함 
        visted[x]=cnt;
        for(int i=0;i<graph.get(x).size();i++){
        	//연결된 노드
            int y = graph.get(x).get(i);
            //방문을 안했을 경우
            if(visted[y]==0){
            	//순차 증가
                cnt++;
                //dfs 실행
                dfs(y);
            }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //정점의 개수
        n = Integer.parseInt(st.nextToken());
        //간선의 개수
        m = Integer.parseInt(st.nextToken());
        //처음 노드
        int r =Integer.parseInt(st.nextToken());
        //연결된 노드 초기화
        for(int i=0;i<n+1;i++){
            graph.add(new ArrayList<Integer>());
        }
        //연결된 노드 체크
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        //노드마다 오름차순
        for(int i=0;i<graph.size();i++){
            Collections.sort(graph.get(i));
        }
        cnt=1;
        visted= new int[n+1];
        dfs(r);
        for(int i=0;i<visted.length;i++){
            if(i!=0) System.out.println(visted[i]);
        }
    }
}