[JAVA] [그래프] 백준 13023번

[JAVA] [그래프] 백준 13023번

반응형

[JAVA] 백준 13023번 - ABCDE

import java.io.*; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static boolean[] visited; //방문여부를 체크하는 배열 static ArrayList[] graph; //친구 관계를 담을 리스트배열 static boolean result = false; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); graph = new ArrayList[N]; visited = new boolean[N]; for (int i = 0; i < N; i++) { //리스트 배열 초기화 graph[i] = new ArrayList(); } for (int j = 0; j < M; j++) { //각각의 사람이 어떤 친구관계를 가지고 있는지 넣어줌 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); } for (int i = 0; i < N; i++) { if (result == false) { dfs(0, i); } } if (result) { bw.write("1"); } else { bw.write("0"); } bw.flush(); bw.close(); } private static void dfs(int depth, int visitedIdx) { //서로 이어지는 친구관계가 4개인지 확인 if (depth == 4) { result = true; return; } visited[visitedIdx] = true; for (int i = 0; i < graph[visitedIdx].size(); i++) { if (visited[graph[visitedIdx].get(i)] == false) { dfs(depth + 1, graph[visitedIdx].get(i)); } } visited[visitedIdx] = false; } }

정답을 맞춘 풀이방법

1. 그래프를 표현하기 위해 ArrayList<>[] 배열을 사용하여 값을 초기화함. ArrayList()> 구조로도 사용가능

2. a, b 가 친구인경우 a.add(b), b.add(a) 처럼 각각 친구 관계를 추가함

3. 그래프를 DFS(깊이우선탐색)방법으로 이어진 친구 관계가 4인 경우를 탐색하고 결과 출력함

반응형

from http://calmdawnstudio.tistory.com/143 by ccl(A) rewrite - 2021-09-07 19:26:54