[백준 / Java] 13023번: ABCDE (골드5)

문제 풀이 날짜: 2023.08.31
포스트 작성일: 2023.08.31

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 13023번: ABCDE (골드5)

 

키워드

DFS, 그래프 탐색

 

풀이 접근법

• A, B, C, D, E 라는 문자에 집중하기보다는, 그래프에서 연달아 4개 이상의 경로가 연결되어 있는지를 확인하면 된다. 즉, DFS의 depth가 4 이상이 되면 된다.
• 44%에서 틀렸습니다를 받은 적 있는데, 실패한 경로에 대한 탐색 기록 삭제하는 작업을 해주어야 한다. 이미 간 경로가 유망하지 않을 때, visited 표시를 복구해주어야 한다.
  • 그런데 이렇게 원복 해주면 방문했던 점을 재방문해서 시간 초과가 난다.
  • 따라서 이전 경로가 유망하지 않을 때만(false를 반환했을 때만) visited를 되돌려주고, 그렇지 않을 때는 그대로 둔다.

 

코드

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

public class Main {

	private static List<Integer>[] graph;
	private static boolean[] visited;
	
	private static int flag = 0;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] temp = br.readLine().split(" ");
		
		int N = Integer.parseInt(temp[0]);
		int M = Integer.parseInt(temp[1]);

		int[] from = {0, 1, 2, 3};
		int[] to = {1, 2, 3, 4};
		
		graph = new ArrayList[N];
		visited = new boolean[N];
		
		for(int i = 0; i < N; i++) {
			graph[i] = new ArrayList<>();
		}
			
		for(int i = 0; i < M; i++) {
			temp = br.readLine().split(" ");
			
			int v = Integer.parseInt(temp[0]);
			int u = Integer.parseInt(temp[1]);
			
			graph[v].add(u);
			graph[u].add(v);
		}
		
		for(int i = 0; i < N; i++) {
			visited[i] = true;
			DFS(i, 0);
			visited = new boolean[N];
		}
		
		System.out.println(flag);
	}

	private static boolean DFS(int start, int depth) {		
		if(depth >= 4) {
			flag = 1;
			return true;
		}
		
		for(int u : graph[start]) {
			if(!visited[u]) {
				visited[u] = true;
				if(!DFS(u, depth + 1)) {
					visited[u] = false;
				}
			}
		}
		
		return false;
	}
}

---

 

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/d37c971dcff078a725f78a2ce49db2b02ecde004/%EB%B0%B1%EC%A4%80/Gold/13023.%E2%80%85ABCDE/ABCDE.java