📍 문제 설명
💡 접근
A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다. 라는 조건을 확인해보면
총 인원이 얼마든 5명의 사람이 각각 순서대로 친구 관계라면 정답인 문제다.
따라서 모든 지점에 대해서 각각 탐색을 해야 한다.
1.탐색 지점을 방문 처리하고 갈 수 있는 정점 중에서 방문하지 않은 정점을 갈 수 있는 만큼 가본다.
2.친구관계를 올바르게 찾지 못했을 경우(갈 수 있는 경로가 더 이상 없는 경우) 타 지점으로도 찾아볼 수 있도록 갔던 곳의 방문 체크를 풀어준다.
3.친구관계 찾았으면 더 볼 필요 없이 바로 끝내버린다.
👩💻 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, m, answer;
static int[][] board;
static int[] arr;
static long[] dp;
static boolean[] visited;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
Main T = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = kb.nextInt();
m = kb.nextInt();
for(int i = 0; i < n; i++) {
list.add(new ArrayList<>());
}
for(int i = 0; i < m; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
list.get(a).add(b);
list.get(b).add(a);
}
System.out.println(list);
for(int i = 0; i < n; i++) {
visited = new boolean[n];
T.solution(0, i);
}
System.out.println(0);
}
private void solution(int L, int start) {
//친구관계 찾았으면 끝내
if (L == 4) {
System.out.println(1);
System.exit(0);
}
visited[start] = true;
//현 지점에서 갈 수 있는 정점 가보기
for (int x : list.get(start)) {
//안 간곳이면 가봐
if (!visited[x]) {
solution(L + 1, x);
}
visited[start] = false;
}
}
}
'Algorithm > baekjoon' 카테고리의 다른 글
연결 요소의 개수 (0) | 2022.02.18 |
---|---|
DFS와 BFS (0) | 2022.02.18 |
연속합 2 (0) | 2022.02.17 |
가장 긴 바이토닉 부분 수열 (0) | 2022.02.16 |
가장 큰 증가 부분수열 (0) | 2022.02.16 |