[백준] 13023 : ABCDE - JAVA

Benjamin·2022년 12월 19일

BAEKJOON

목록 보기

25/71

🙋🏻‍♀️DFS 이용!

문제분석

N,M의 최대범위가 2000이므로 인접리스트를 썼을 때 시간복잡도는 O(4000)이다.
이를 모든 노드에 진행했을때 2000 * 4000 = 8000000이므로 DFS를 사용해도 된다.주어진 모든 노드에 DFS 수행재귀의 깊이가 5이상(5개의 노드가 재귀 형태로 연결)이면 1, 아니면 0을 출력한다.

Troubleshooting

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

public class Main {
static ArrayList<Integer>[] freind;
static boolean[] visited;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		freind = new ArrayList[N];
		for(int i =0; i<N; i++) {
			freind[i] = new ArrayList<>();
		}
		sc.nextLine();
		for(int i =0; i<M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
		    freind[a].add(b);
		    freind[b].add(a);
		    sc.nextLine();
		}
		visited = new boolean[N];
		for(int i =0; i<N; i++) {
			int answer = DFS(i,1);
			if(answer == 1) {
		    	System.out.println("1");
		        return;
		    }
			for(int j=0; j<N; j++) {
				visited[j] = false;
			}
		}
		System.out.println("0");
		return;
	}
	public static int DFS(int person,int depth){
	    if(depth == 5) {
	    	return 1;
	    }
	    visited[person] = true;
	    for(int i : freind[person]) {
	    	if(!visited[i]) {
            	depth++;
	    		DFS(i,depth);
	        }
	    }
	    return 0;
	}
}

문제

어떤 예제를 넣든 무조건 0이 출력됐다.

원인

어떤 하나의 루트를 쭉 검사하다가, 친구검사가 다 끝나서 depth를 하나 이전으로 가서 그 다음부분을 검사할때는 depth도 동일하게 -1이 되어야하는데, 그렇지않고 어떤 상황이든 depth가 계속 누적되어서 가능하지않은경우에도 depth가 누적되며, 검사하는 경우의수가 5번 초과이면 마지막줄의 return 0이 실행돼서 그런것이다.

해결

for문 내에서 depth 변수를 갱신하고 그 값을 파라미터로 넣는 행위는 위험하다!!
DFS를 재귀호출할 때, 파라미터에서 값을 계산하고, 갱신해주는일은 하지말자.
DFS(i,depth+1) 로 수정했다.

Troubleshooting 2

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

public class Main {
static ArrayList<Integer>[] freind;
static boolean[] visited;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		freind = new ArrayList[N];
		for(int i =0; i<N; i++) {
			freind[i] = new ArrayList<>();
		}
		sc.nextLine();
		for(int i =0; i<M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
		    freind[a].add(b);
		    freind[b].add(a);
		    sc.nextLine();
		}
		visited = new boolean[N];
		for(int i =0; i<N; i++) {
			int answer = DFS(i,1);
			if(answer == 1) {
		    	System.out.println("1");
		        return;
		    }
			for(int j=0; j<N; j++) {
				visited[j] = false;
			}
		}
		System.out.println("0");
		return;
	}
	public static int DFS(int person,int depth){
	    if(depth == 5) {
	    	return 1;
	    }
	    visited[person] = true;
	    for(int i : freind[person]) {
	    	if(!visited[i]) {
	    		DFS(i,depth+1);
	        }
	    }
	    return 0;
	}
}

문제

그래도 여전히 1이 나와야하는 예제에서 0이 출력된다.

원인

depth가 5를 찍으면 return1이 되고, 그 후 재귀호출을 빠져나오며 이전 depth들이 적용되어 최종적으로 0이 출력되는것이었다.

해결

DFS를 호출하며, 한 번 1을 찍은후에는 계속 return 1을 유지할 수 있도록, DFS 재귀호출에 조건을 걸어주고, 해당 경우에는 return 1이 되도록 했다.

if(DFS(i,depth+1) ==1) {
	    			return 1;
	    		}

Troubleshooting 3

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

public class Main {
static ArrayList<Integer>[] freind;
static boolean[] visited;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		freind = new ArrayList[N];
		for(int i =0; i<N; i++) {
			freind[i] = new ArrayList<>();
		}
		sc.nextLine();
		for(int i =0; i<M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
		    freind[a].add(b);
		    freind[b].add(a);
		    sc.nextLine();
		}
		visited = new boolean[N];
		for(int i =0; i<N; i++) {
			int answer = DFS(i,1);
			if(answer == 1) {
		    	System.out.println("1");
		        return;
		    }
			for(int j=0; j<N; j++) {
				visited[j] = false;
			}
		}
		System.out.println("0");
		return;
	}
	public static int DFS(int person,int depth){
	    if(depth == 5) {
	    	return 1;
	    }
	    visited[person] = true;
	    for(int i : freind[person]) {
	    	if(!visited[i]) {
	    		if(DFS(i,depth+1) ==1) {
	    			return 1;
	    		}
	        }
	    }
	    return 0;
	}
}

문제

예제는 다 맞았는데, 백준에서 틀렸다.

원인

depth5까지 검사를 진행했는데, 불가능한 경우에는 이전 재귀호출(depth == 4)로 돌아가서 다음 노드를 검사한다. 이렇게 돌아갈 경우에는 depth만 줄어들게아니라 depth가 4인 이전 노드가 false로 바뀌어야한다. 그렇지않으면 이후검사에서 해당 노드가 계속 제외되기때문이다.

해결

DFS에서 마지막에 return 0하기전에 해당 노드에서 불가능할경우, DFS 호출시 True로 바꾸었던 방문배열의 해당노드를 다시 false로 바꿔주는 코드를 추가했다.
visited[person] = false;

제출코드

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

public class Main {
static ArrayList<Integer>[] freind;
static boolean[] visited;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		freind = new ArrayList[N];
		for(int i =0; i<N; i++) {
			freind[i] = new ArrayList<>();
		}
		sc.nextLine();
		for(int i =0; i<M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
		    freind[a].add(b);
		    freind[b].add(a);
		    sc.nextLine();
		}
		visited = new boolean[N];
		for(int i =0; i<N; i++) {
			int answer = DFS(i,1);
			if(answer == 1) {
		    	System.out.println("1");
		        return;
		    }
			for(int j=0; j<N; j++) {
				visited[j] = false;
			}
		}
		System.out.println("0");
		return;
	}
	public static int DFS(int person,int depth){
	    if(depth == 5) {
	    	return 1;
	    }
	    visited[person] = true;
	    for(int i : freind[person]) {
	    	if(!visited[i]) {
	    		if(DFS(i,depth+1) ==1) {
	    			return 1;
	    		}
	        }
	    }
        visited[person] = false;
	    return 0;
	}
}

코드 수정

main함수의 for문에서 DFS를 실행하고난 후 visited를 false로 초기화시켜주는데, 이 작업은 필요없다.
depth 5를 찍은 노드는 True로 남겠지만, 결과적으로 더이상 DFS를 호출하지않기때문에 그 부분은 문제가되지않으며, depth 5를 찍지않아서 더 검사가 필요할경우에는 DFS함수의 마지막에 visited[person] = false;를 하기때문에 결국 depth5를 제외한 모든 노드들은 false로 변경되기때문이다.

주의할 사항

for문 변수 갱신!
재귀호출은 그 과정에서 답을 찾았을 경우, 다시 이전에 호출했던 곳으로 돌아가는 작업도 수행되므로 그 때 return값으로 답이 갱신되지않도록 주의해야한다!!
-> depth를 따져야하면 호출했던 곳으로 돌아가는부분을 반드시 고려해서 코드를 짜야한다.
depth를 고려하지않고, 방문배열만 체크하면 돌아가는 부분을 고려하지않아도된다.