[BOJ] - ABCDE / 13023번 (Java)

[BOJ] - ABCDE / 13023번 (Java)

[BOJ] - ABCDE / 13023번 (Java)

1. 문제 접근

A-B-C-D-E와 같은 친구 관계가 있는지 확인하는 문제다.

 

DFS를 이용하여 해결할 수 있다.

 

0번 노드부터 N-1번 노드까지 순차적으로 DFS의 시작점으로 하여 탐색을 진행한다.

 

`isCorrectConnection()`메소드를 호출할 때 탐색을 시작할 노드(`nodeNum`)과 현재 연결된 친구 수(`0`)을 함께 전달한다.

 

// 0번 정점부터 N-1번 정점까지 DFS 순회
for (int nodeNum = 0; nodeNum < N; ++nodeNum) {
    isVisited = new boolean[N];
    isCorrectConnection(nodeNum, 0);
    // 이미 조건을 만족한 경우 탈출
    if (flag)
        break;
}

 

DFS 탐색의 기저조건은 연결된 친구의 길이가 5가 될 때이다. 즉, DFS의 깊이가 5가 되면 A-B-C-D-E와 같은 친구 관계가 존재한다는 것을 의미한다.

 

private static void isCorrectConnection(int currNode, int depth) {
    // 기저조건(친구관계 만족: 연결이 5개다)
    if (depth == 5) {
        flag = true;
        return;
    }
    ...
}

 

또한, DFS탐색을 하며 방문처리에 신경 써야한다.

 

DFS를 호출 한 뒤, 해당 노드가 이미 방문한 적이 있다면 반환해야하고, 방문한 적이 없다면 방문처리를 해야한다.

 

뿐만 아니라 메소드가 종료 될 때 현재 방문한 노드에 대해 방문 처리를 취소해야 다른 경로로 탐색을 할 때 문제가 되지 않는다.

 

private static void isCorrectConnection(int currNode, int depth) {
    ...
    // 해당 노드를 방문한 적이 있으면 반환
    if (isVisited[currNode]) {
        return;
    }

    isVisited[currNode] = true;
    ... // 로직
    isVisited[currNode] = false;
}

---

2. 코드

package boj;

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

/**
 * [BOJ] - ABCDE / 13023번 
 * @author JinHxxxxKim
 * 
 * 1. 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)을 입력받는다.
 * 2. 친구 관계를 입력받는다.
 * 3. 각 정점에서 DFS 탐색을 진행한다.
 * 		- 재귀의 깊이가 5가 될 경우 문제의 조건이 만족된 것이므로 종료한다.
 */
public class Sol_13023 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringTokenizer st;

	private static List<Integer>[] adList;
	private static boolean[] isVisited;
	private static int N, M;
	private static boolean flag; // 만족하는 친구관계가 있는지 판별 플래그

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine().trim());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		adList = new List[N];
		isVisited = new boolean[N];
		for (int idx = 0; idx < N; ++idx) {
			adList[idx] = new ArrayList<>();
		}

		// 간선정보 저장
		for (int edgeCnt = 0; edgeCnt < M; ++edgeCnt) {
			st = new StringTokenizer(br.readLine().trim());
			int node1 = Integer.parseInt(st.nextToken());
			int node2 = Integer.parseInt(st.nextToken());
			adList[node1].add(node2);
			adList[node2].add(node1);
		}

		// 0번 정점부터 N-1번 정점까지 DFS 순회
		for (int nodeNum = 0; nodeNum < N; ++nodeNum) {
			isVisited = new boolean[N];
			isCorrectConnection(nodeNum, 0);
			// 이미 조건을 만족한 경우 탈출
			if (flag)
				break;
		}

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

	private static void isCorrectConnection(int currNode, int depth) {
		// 기저조건(친구관계 만족: 연결이 5개다)
		if (depth == 5) {
			flag = true;
			return;
		}
		// 이미 조건을 만족한 경우
		if (flag) {
			return;
		}
		// 해당 노드를 방문한 적이 있으면 반환
		if (isVisited[currNode]) {
			return;
		}

		isVisited[currNode] = true;
		// 인접 노드 탐색
		for (int adNode : adList[currNode]) {
			isCorrectConnection(adNode, depth + 1);
		}
		isVisited[currNode] = false;
	}
}

---

3. 디버깅

DFS 탐색을 진행하며 노드의 방문처리를 신경써서 해줘야 한다.

 

해당 DFS 메소드가 종료되었다는 것은 해당 노드를 선택할 경우 가능한 모든 경우를 따져 보았다는 것을 의미한다.

 

따라서 이후 다른 경로로 즉, 이전 선택이 변경 되었을 때 해당 노드를 다시 방문할 가능성이 있기에 반드시 방문처리를 취소해야 한다.

 

---

4. 결과