[백준] 13023번 ABCDE JAVA (자바) 풀이

문제 13023번 (dfs, 백트래킹)

 

 : 총 N명이 참가

   사람들은 0번 ~ N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구

• 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을 출력

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 

 

 조건1  백트래킹의 뚜렷한 조건은 없다 고로 dfs가 더 맞다고 봐야한다

 

 종료 조건) depth==4

 관계를 타고타고 들어가 depth가 4가 된다면 조건을 충족하므로 check를 true로 설정한다

 

 1. 시작지점은 for문을 통해 0 ~ 9까지 넣고 node로 받는다

 시작 지점인 0 ~ 9 에서 순차적으로 dfs 돌리고 next를 정한다

 깊이를 증가하면서 다음지점을 dfs로 넣어본다

 

 2. check를 통해 결과 출력

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,M;
    static boolean visit[],check;
    static List<Integer>[] friend;
    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());
        
        friend = new ArrayList[N];
        for(int i=0;i<N;i++){
            friend[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());
            friend[a].add(b);
            friend[b].add(a);
        }
        
        visit = new boolean[N];
        for(int i=0;i<N;i++){
            if(!check){
                visit[i]=true;  
                dfs(i,0);
                visit[i]=false;
            }
        }
        System.out.println(check?1:0);
    }
    
    static void dfs(int node, int depth){
        if(depth==4){
            check = true;
            return;
        }
        
        for(int next:friend[node]){
            if(!visit[next]){
                visit[next]=true;
                dfs(next, depth+1);
                visit[next]=false;
            }
        }
    }
}

 

 [해설]
     

 :  static int N,M;
    static boolean visit[],check;
    static List<Integer>[] friend;
    

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());  총 인원
    M = Integer.parseInt(st.nextToken());  관계 수
        
 :  friend = new ArrayList[N];  친구관계를 저장할 배열
    for(int i=0;i<N;i++){
            friend[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());
            friend[a].add(b);  서로의 친구관계 저장
            friend[b].add(a);  서로의 친구관계 저장
    }
        
 :  visit = new boolean[N];  방문기록 초기화
    for(int i=0;i<N;i++){
            if(!check){  check가 false 즉 depth가 아직 4가 채워지지 않을 경우에 실행
                visit[i]=true;  
                dfs(i,0);  dfs 실행
                visit[i]=false;
            }
    }
    System.out.println(check?1:0);  check가 true일 경우에만 1출력
    
    
 :  static void dfs(int node, int depth){  현지점, 깊이
        if(depth==4){  종료조건
            check = true;
            return;
        }
        
        for(int next:friend[node]){  현지점에서 연결된 모든 친구들 검사
            if(!visit[next]){  방문 전이라면 dfs 실행하면서 더 깊이 내려간다
                visit[next]=true;
                dfs(next, depth+1);  depth 카운트
                visit[next]=false;
            }
        }
    }


  

 

 

 

 

이제 풀어보러 갈께요 :)

 

https://www.acmicpc.net/problem/13023

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *