[백준 JAVA]13023 ABCDE

문제

---

13023번: ABCDE (acmicpc.net)

13023번: ABCDE

 

 

dfs를 활용해서 이어진 친구들을 세주었다.

풀이방법

---

• 무방향 그래프이기 때문에 배열 양쪽에 값을 넣어준다.
  • list[to].add(from);
    list[from].add(to);
• 입력을 받고 dfs를 돌려준다.
• 인접한 경우를 재귀호출을 사용하며 count를 세준다.
• count가 5가되면(관계가 5명 이어지면) return 을 해주고 end를 true로 바꿔준다.

코드

---

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>[] list;
	static int friend[];
	static int N;
	static boolean end;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader 	br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		
		
		list = new ArrayList[N];
		
		for (int i = 0; i <N; i++) {
			list[i] = new ArrayList<>();
		}

		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int from=Integer.parseInt(st.nextToken());
			int to=Integer.parseInt(st.nextToken());
			list[from].add(to);
			list[to].add(from);
		}
		

		
		for(int i=0; i<N; i++) {
			boolean visit[]=new boolean[N];
			dfs(i,visit,0);
			if(end==true) {
				System.out.println("1");
				break;
			}
			
		}
		if(end==false) {
			System.out.println("0");
		}
	}
	
	static void dfs(int cur, boolean[] visit,int count) {
		visit[cur]=true;
//		System.out.println(cur);
		count++;
		if(count==5) {
			end=true;
			return;
		}

		for(int i=0; i<list[cur].size(); i++) {
            if(!visit[list[cur].get(i)]) { //방문하지 않았으며 인접한 경우
                dfs(list[cur].get(i),visit,count);
                visit[list[cur].get(i)]=false;
            }
        }
		
		return;
	}

}