[1976] 여행 가자 (feat.DFS,BFS)

##  백준 Gold IV [1976] 여행 가자

* 자료 구조

* 그래프 이론

* 그래프 탐색

* 분리 집합

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

1976번: 여행 가자

 

 

 

헷갈렸던점

 

-자기 자신이 0 인점

 

2

2

0 0

0 0

1 1

 

-> YES 나와야함

 

 

- 그래프가 연결되어있지 않지만  여행이 가능한 경우

 

5
2
0 1 1 0 0
1 0 0 0 0
1 0 0 0 0
0 0 0 0 1
0 0 0 1 0
4 5

 

-> YES 나와야함

 

 

 

 

DFS, BFS 풀이

 

 

BFS

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


// 행렬 or List
// bfs 행렬 

public class boj1976_bfs{
    
    static int node=0;
    static int targetCnt=0;
    static boolean[] visited;

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        node = Integer.parseInt(br.readLine()); 
        targetCnt = Integer.parseInt(br.readLine());
        

        String[][] city = new String[node][node];
        boolean[] visited = new boolean[node];

        // 행렬 받기
        for(int i=0; i<node; i++){
            city[i]=br.readLine().split(" ");
            //city[i][i]="1";
        }
        // 타겟 시티
        String[] targetCity = br.readLine().split(" ");

        int cnt=0;
        // 모든 도시 BFS 해야됨
        for(int i=0;i<node;i++){
            
            BFS(i,city,visited);

            // 타겟 도시 방문 여부 확인
            for(int j=0; j<targetCnt;j++){
                if(visited[Integer.parseInt(targetCity[j])-1]==true){
                    cnt++;
                }
            }
            if(cnt==targetCnt){
                bw.write("YES");
                bw.flush();
                return;
            }
            // yes가 아니니까 다시 초기화
            visited = new boolean[node+1];    
            cnt=0;
        }
        //BFs 끝났는데 YES가 안나왔으니까
        bw.write("NO");
        bw.flush();
    }

    public static void BFS(int idx, String[][] city,boolean[] visited){
        Queue<Integer> q = new LinkedList<>();

        visited[idx]=true; // 방문 체크
        q.add(idx); // 큐에넣고
        while(!q.isEmpty()){
            int now = q.poll();
            for(int i=0;i<node;i++){
                if(now==i)  continue;
                // 연결되어있고 방문한적없으면
                if(city[now][i].equals("1") && visited[i]==false){
                    visited[i]=true; // 방문체크
                    q.add(i); // 큐에 더해주기
                }
            }
            
        }
    }
}

 

 

DFS

import java.io.*;


// 행렬 or List
// dfs행렬

public class boj1976_dfs{
    
    static int node=0;
    static int targetCnt=0;
    static boolean[] visited;

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        node = Integer.parseInt(br.readLine()); 
        targetCnt = Integer.parseInt(br.readLine());
        

        String[][] city = new String[node][node];
        boolean[] visited = new boolean[node];

        // 행렬 받기
        for(int i=0; i<node; i++){
            city[i]=br.readLine().split(" ");
            //city[i][i]="1";
        }
        // 타겟 시티
        String[] targetCity = br.readLine().split(" ");

        int cnt=0;
        // 모든 도시 DFS 해야됨
        for(int i=0;i<node;i++){
            
            DFS(i,city,visited);

            // 확인
            for(int j=0; j<targetCnt;j++){
                if(visited[Integer.parseInt(targetCity[j])-1]==true){
                    cnt++;
                }
            }
            if(cnt==targetCnt){
                bw.write("YES");
                bw.flush();
                return;
            }
            // yes가 아니니까 다시 초기화
            visited = new boolean[node+1];    
            cnt=0;
        }
        //DFS 끝났는데 YES가 안나왔으니까
        bw.write("NO");
        bw.flush();
    }

    public static void DFS(int idx, String[][] city,boolean[] visited){
        
        visited[idx]=true; // 자기자신 방문처리해줘야돼
        
        for(int i=0; i<node;i++){
            if(city[idx][i].equals("1") && visited[i]==false){
                visited[i]=true;
                DFS(i,city,visited);
            }
        }
    }
}