백준 13923번: ABCDE [JAVA]

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

13023번: ABCDE

• 풀이

처음에는 문제가 잘 이해되지 않았지만, 결론적으로 이 문제는 연속으로 이어진 5개의 노드가 있는지 확인하는 문제이다. 따라서, DFS를 이용해 연결된 5개의 노드가 있는지 확인하면 된다.

for 문을 이용해 0~N-1번을 각각 시작점으로 둔다. 그리고 인접한 노드를 찾은 뒤, 방문하지 않았다면 다시 인접 노드를 탐색한다. 이렇게 쭉 들어가다가 5번째 노드를 찾으면 종료하고, 찾지 못 했다면 이전의 노드로 돌아온다. 이 때, 이전 노드로 돌아왔다면 방금 찾았던 노드는 방문 체크를 해제해줘야 한다. 모든 경로를 탐색해봤는데도 5개의 이어지는 경로를 찾지 못 했다면 0을 출력한다.

• 코드

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

public class Main {
	static ArrayList <Integer> [] arr;
	static int N, M;
	static int flag; // 5개 이어지는 노드의 존재 여부
	static boolean isSelected [];
	
	static void findFriends(int start, int r) {
		if (r == 5 || flag == 1) { // 연속된 다섯 친구를 구했거나, 이미 구한 경우 종료
			flag = 1;
			return;
		}
		
		for (int i : arr[start]) { // 방문하지 않은 인접 노드 탐색
			if (isSelected[i]) continue;
			isSelected[i] = true; // 방문 노드 저장
			findFriends(i, r+1);
			isSelected[i] = false; // 되돌아온 노드 삭제
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		// 입력 및 초기화
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new ArrayList[N];
		for (int i=0; i<N; i++) arr[i] = new ArrayList<Integer>();
		
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a].add(b);
			arr[b].add(a);
		}
		
		for (int i=0; i<N; i++) { // 모든 점을 시작점으로 돌며 함수 실행
			isSelected = new boolean[N];
			isSelected[i] = true;
			findFriends(i, 1);
		}
		
			System.out.println(flag); // 출력 
	}
}