[백준] 13203 - ABCDE (Java)

[백준] 13203 - ABCDE (Java)

문제

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

풀이/후기

단순 DFS가 아닌 고려해야할 것이 많은 문제

- DFS로 해당 경로 탐색 시 5 이상의 경로가 아니면 방문처리를 다시 false로 수정 필요

: 직접 반례 케이스를 찾아봐야함

- 시간초과

: 구글링으로 고려해야할 부분도 다 고려해줬는데 계속 시간초과가 발생했음

: 모두 배열 형태의 ArrayList를 사용했는데, 난 구조상 이차원배열을 사용해도 될 것 같다고 판단하고 계속 고집함

결국 이차원배열을 ArrayList로 바꾸자마자 정답 처리가 되었다는 후기,,^^; 남들이 안한 이유는 다 있다,,

list를 사용해야 시간초과가 나지 않는 이유는 dfs내에서 반복문을 돌 때 N번을 모두 도냐 항목이 있는 만큼만 도냐이기 때문에 잘 생각해보면 반복문 반복 횟수부터 다르다는 것을 알 수 있다!

코드

package GraphTheory;

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

public class Problem13023 {

	static int N, M;
	//static int[][] arr;
	static ArrayList<Integer>[] list;
	static boolean[] visited;
	static int result = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(str.nextToken());
		M = Integer.parseInt(str.nextToken());

		//arr = new int[N][N];
		list = new ArrayList[N];
		visited = new boolean[N];
		
		for (int i=0; i<N; i++) {
			list[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < M; i++) {
			str = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(str.nextToken());
			int y = Integer.parseInt(str.nextToken());
			list[x].add(y);
			list[y].add(x);
		}

		// dfs
		for (int i = 0; i < N; i++) {
			if (result == 0) {
				dfsFn(i, 1);
			}

		}

		System.out.println(result);
	}

	static void dfsFn(int x, int count) {
		
		//ABCDE가 친구이려면 깊이가 5여야 함
		if (count == 5) {
			result = 1;
			return;
		}

		visited[x] = true;
		for (int j : list[x]) {
			if (!visited[j]) {
				dfsFn(j, count+1);
			}
		}
		visited[x] = false;
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/3ac00753e452afc6d896d1e8f4b85d02b8b3d34e

참고

https://minhamina.tistory.com/50

https://velog.io/@beberiche/BOJ-13023-ABCDE

https://hanyeop.tistory.com/419