99클럽 코테 스터디 4일차 TIL DFS(알고리즘 수업 - 깊이 우선 탐색 1)

https://www.acmicpc.net/problem/24479

 

자칭 DFS, BFS 기계로서,, 문제 읽고 10분만에 구현 끝냈는데,, 제출하니 1초만에 틀렸다고 나왔다,,

아무리 이것저것 테케 넣어봐도 맞는데,, 하다가 발견했다 내가 문제를 잘못 이해했다는 것을,,!!!

말 그대로 방문순서를 저장했었어야 했는데 나는 DFS 재귀에 cnt 넣어서 시작점으로부터 거리가 얼마나 떨어져 있는 지를 저장하고 있었음,,

무튼 이거 제외하면 단순 DFS 구현 문제였다!

다만, 오름차순 정렬만 주의 하면 된다.

 

아래가 제출 코드(정답)이고,

package STUDY;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Day04_BOJ_24479 {

    static int n, m, r;
    static int cnt;
    static List<Integer>[] list;
    static int[] visit;

    public static void dfs(int x){
        visit[x] = ++cnt;
        for(int i=0; i<list[x].size(); i++){
            int now = list[x].get(i);
            if(visit[now] != 0) continue;
            dfs(now);
        }
    }

    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());
        r = Integer.parseInt(st.nextToken());
        // 2차원 리스트 초기화
        list = new ArrayList[n+1];
        for(int i=0; i<n+1; i++){
            list[i] = new ArrayList<>();
        }
        // 간선 정보
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }
        // 오름차순 배열
        for(int i=0; i<n+1; i++){
            Collections.sort(list[i]);
        }
        visit = new int[n+1];
        dfs(r);
        // 출력
        for(int i=1; i<n+1; i++){
            System.out.println(visit[i]);
        }
    }
}

 

이 아래는 처음에 잘 못 이해하고 구현했던 잘못된 코드,,(dfs 함수만 다름)

public static void dfs(int x, int cnt){
    visit[x] = cnt;
    for(int i=0; i<list[x].size(); i++){
        int now = list[x].get(i);
        if(visit[now] != 0) continue;
        dfs(now, cnt+1);
    }
}

 

아 그리고 추가로!! sysout 대신 stringbuilder 사용해보면 시간이 얼마나 줄어들까해서 해봤는데 2배로 줄어들음.;;

마지막 출력만 요렇게 변경해주었다

 

// 출력
StringBuilder sb = new StringBuilder();
for(int i=1; i<n+1; i++){
	sb.append(visit[i] + "\n");
}
System.out.println(sb.toString());