[백준] 13023번 : ABCDE Gold5(골드5) - JAVA[자바]

[Gold V] ABCDE - 13023

문제 링크

성능 요약

메모리: 19592 KB, 시간: 212 ms

분류

백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 1월 29일 17:16:40

문제 설명

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

접근 방법

1. 모든 노드 중 홉이 5개이상인 노드가 있다면 유효한 상황이고 아니라면 0

2. DFS를 통해서 체크를 한 뒤 카운트가 5개이상이라면 출력 후 종료

3. 마지막까지 없다면 0을 출력한다.

 

백트래킹

// 관련노드가 5개이상인지 확인하는 로직
	private static void searchABCDE(int pos, int count) {
		// 홉의 개수가 5개이상이라면 1 출력 후 종료
		if(count == 5) {
			System.out.println("1");
			System.exit(0);
		}
		
		// 현재 위치에서 갈 수 있는 노드만 조사
		for(int next : graph[pos]) {
			// 이미 방문한 노드라면 넘어간다.
			if(visit[next]) continue;
			// 방문하지 않았다면 방문 처리 후 재귀 호출
			visit[next] = true;
			searchABCDE(next,count+1);
			// 다시 원래 상태로 복구
			visit[next] = false;
		}
	}

 

풀이코드

package step1;

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

public class Main {
	// 노드의 개수, 입력받을 간선의 개수
	static int n,m;
	// ArrayList 배열을 이용한 그래프
	static ArrayList<Integer>[] graph;
	// 방문처리하기 위한 배열
	static boolean[] visit;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		visit = new boolean[n];
		graph = new ArrayList[n];
		for(int i = 0; i < n; i++) {
			graph[i] = new ArrayList<>();
		}
		
		// 양방향 노드
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a].add(b);
			graph[b].add(a);
		}
		
		// N이 다섯개보다 적다면 유효하지않으므로 0출력 후 리턴
		if(n < 5) {
			System.out.println(0);
			return;
		}
		
		for(int i = 0; i < n; i++) {
			// 현재 시작노드는 방문처리
			visit[i] = true;
			searchABCDE(i,1);
			visit[i] = false;
			// 방문하지 않았음으로 초기화
		}
		System.out.println(0);
	}
	
	// 관련노드가 5개이상인지 확인하는 로직
	private static void searchABCDE(int pos, int count) {
		// 홉의 개수가 5개이상이라면 1 출력 후 종료
		if(count == 5) {
			System.out.println("1");
			System.exit(0);
		}
		
		// 현재 위치에서 갈 수 있는 노드만 조사
		for(int next : graph[pos]) {
			// 이미 방문한 노드라면 넘어간다.
			if(visit[next]) continue;
			// 방문하지 않았다면 방문 처리 후 재귀 호출
			visit[next] = true;
			searchABCDE(next,count+1);
			// 다시 원래 상태로 복구
			visit[next] = false;
		}
	}
}