알고리즘/백준

13023_ABCDE

베리영young 2024. 8. 20. 20:28

사용 알고리즘: dfs

사용 언어: java

 

대체 문제가 뭔지 싶었다.

5개 관계가 일렬로 이어진 관계를 찾으라는 것

 

그리고 그러한 관계가 하나라도 있으면 1을 출력. 즉, 찾으면 멈춰라

 

package ssafyAlgorithm;

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

public class Main_bj_13023_ABCDE {
	static int n, m, ans;
	static ArrayList<Integer>[] al;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt(); //사람 수(0부터 시작)
		m = sc.nextInt(); //한 그룹에 m명
		al = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			al[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			al[a].add(b);
			al[b].add(a);
		}
		//입력 끝
		
		for (int i = 0; i < n; i++) {
			boolean[] visit = new boolean[n];
			visit[i] = true;
			dfs_abcde(i, 1, visit);
			if(ans > 0) break;
		}
		
		if(ans > 0) System.out.println(1);
		else System.out.println(0);
	}

	private static void dfs_abcde(int node, int dept, boolean[] visit) {
		if(dept == 5) {
			ans++;
			return;
		}
		
		for(int nxt : al[node]) {
			if(!visit[nxt]) {
				visit[nxt] = true;
				dfs_abcde(nxt, dept+1, visit);
				visit[nxt] = false;
			}
		}
	}

}

'알고리즘 > 백준' 카테고리의 다른 글

1697_숨바꼭질 * (맞았는데 다시 풀면 또 틀리려나;)  (0) 2024.08.22
15683_감시  (0) 2024.08.20
1753_최단경로  (0) 2024.08.20
1068_트리  (0) 2024.08.14
20166_문자열 지옥에 빠진 호석  (1) 2024.08.12