[백준]2750 수 정렬하기 2 - 자바/Java

13023번: ABCDE

🌱풀이

알고리즘

1. 각 사람을 기준으로 DFS를 돌며, 깊이가 5에 도달하는 경우가 있는지를 확인한다.
2. 확인을 위해 arrive라는 boolean형 변수를 선언하여 종료 조건에서 true로 바꾼다.
3. 인접 리스트를 선언하여 무방향 그래프를 표현한다.
4. 특이하게도 visited 배열을 true로 바꿨다가 해당 에지의 탐색이 종료되면 false로 초기화한다. 이는 0번 사람을 기준으로는 깊이 5가 나오지 않을지라도 4번 사람을 기준으로는 깊이 5가 나올 수 있기 때문이다. 예제 2번에서 확인할 수 있다.
5. 단순하게 에지를 한번씩 탐색하는게 목적이라면 false로 바꿔주지 않아도 된다. 하지만 이번 문제처럼 각 에지별 깊이를 알고 싶거나 하는 등의 더 많은 방문을 필요로 하는 경우에는 초기화 과정이 필요하다.

메모리 : 39528KB, 시간 : 400ms

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	//깊이가 5 이상인 DFS을 찾는 문제다.
	static boolean visited[];
	static ArrayList<Integer>[] A;
	static boolean arrive;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		arrive = false;
		int N = sc.nextInt(); //사람의 수
		int M = sc.nextInt(); //관계의 수
		A = new ArrayList[N];
		visited = new boolean[N];
		for(int i = 0; i<N; i++) A[i] = new ArrayList<Integer>();
		for(int i = 0; i<M; i++) {
			int s = sc.nextInt();
			int e = sc.nextInt();
			A[s].add(e);
			A[e].add(s);
		}
		for(int i = 0; i<N; i++) {
			DFS(i, 1); //i는 사람의 번호, 1은 최초 깊이
			if(arrive) break;
		}
		if(arrive) System.out.print("1");
		else System.out.print("0");
	}
	static void DFS(int now, int depth) {
		if(depth == 5 || arrive) {
			arrive = true;
			return;
		}
		visited[now] = true;
		for(int i : A[now]) {
			if(visited[i]) continue;
			DFS(i, depth+1);
		}
		visited[now] = false;
	}
}

---

🪴코드 리뷰

🌿메모리 : 38512KB, 시간 : 512ms

DFS 재귀 함수가 true로 반환되며 종료되려면 인접 리스트에 접근하고 난 뒤에야 가능하므로, 연산량이 증가한 것으로 보인다. 이는 DFS 메소드 내부에 인접 리스트를 꺼내는 반복문에 종료 확인 조건이 또 존재하기 때문이다.

💡 풀이자 : dyffh1031

import java.util.*;

public class Main {
    static boolean[] visited;
    static ArrayList<Integer>[] adj;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        visited = new boolean[n];
        int m = sc.nextInt();
        adj = new ArrayList[n];
        for(int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for(int i = 0; i < m; i++) {
            int num1 = sc.nextInt();
            int num2 = sc.nextInt();
            adj[num1].add(num2);
            adj[num2].add(num1);
        }
        for (int i = 0; i < n; i++) {
            if(dfs(i,1)) {
                System.out.println(1);
                return;
            }
        }
        System.out.println(0);
    }

    private static boolean dfs(int curr, int depth) {
        if(depth == 5) {
            return true;
        }
        visited[curr] = true;
        for(int next : adj[curr]) {
            if(visited[next]) continue;
            if(dfs(next, depth+1)) return true;
        }
        visited[curr] = false;
        return false;
    }
}

---

🌿메모리 : 14996KB, 시간 : 228ms

BufferedReader를 사용해서 시간이 줄은 것으로 보인다. 이 외에도 인접 리스트를 사용자 정의 자료구조 Node로 선언한 것이 특징이다. 근데 이건 인접 리스트라기보다는 인접 배열 + 사용자 정의 클래스다.

💡 풀이자 : pjys211

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

public class Main{
    public static int N, M;
    public static Node[] nodeList;
    public static boolean[] visited;
    public static boolean possible;
    public static class Node{
        int num;
        Node node;
        public Node(int num, Node node){
            this.num = num;
            this.node = node;
        }
    }
    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());

        nodeList = new Node[N];
        visited = new boolean[N];
        possible = false;
        for (int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            nodeList[from] = new Node(to,nodeList[from]);
            nodeList[to] = new Node(from,nodeList[to]);
        }
        for (int num = 0; num < N; num++){
            visited[num] = true;
            DFS(num,1);
            visited[num] = false;

        }

        if (possible){
            System.out.println(1);
        }else{
            System.out.println(0);
        }

    }

    public static void DFS(int num, int count){
        if(count == 5){
            possible = true;
            return;
        }
        if(possible){
            return;
        }

        for (Node temp = nodeList[num]; temp != null; temp = temp.node){
            if(visited[temp.num]) continue;
            count++;
            visited[temp.num] = true;
            DFS(temp.num, count);
            count--;
            visited[temp.num] = false;
        }
    }
}

---

🌿메모리 : 16908KB, 시간 : 200ms

이 사람은 인접 리스트가 불필요하게 선언되지 않도록 존재하는 친구들을 기준으로만 선언했다. if(arr[a]==null) 이 조건에서 알 수 있다.

💡 풀이자 : kws04254

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		List<Integer> [] arr = new ArrayList[N];
		for(int i=0; i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(arr[a]==null) {
				arr[a] = new ArrayList<Integer>();
			}
			if(arr[b]==null) {
				arr[b] = new ArrayList<Integer>();
			}
			arr[a].add(b);
			arr[b].add(a);
		}
		boolean check[];
		for(int i=0; i<N;i++) {
			check = new boolean[N];
			check[i] =true;
			if(dfs(arr, check, 0, i)) {
				System.out.println(1);
				return;
			}
		}
		System.out.println(0);
	}
	public static boolean dfs(List<Integer> [] arr, boolean[] check, int num, int cur) {
		if(num==4) {
			return true;
		}
		if(arr[cur]==null) return false;
		for(int i=0; i< arr[cur].size();i++) {
			int next = arr[cur].get(i);
			if(check[next]) continue;
			check[next] = true;
			if(dfs(arr,check,num+1,next)) return true;
			check[next] = false;
		}
		return false;
	}
}

---

Conclusion

• DFS에서 방문 배열을 초기화 하는 경우의 수를 생각해볼 수 있었다.