백준 11581 (구호물자)

문제

11581번: 구호물자

N개의 정점이 주어지면 1번 부터 시작하여 N번까지 가는제 Cycle이 있는지 없는지 판별하는 문제이다.

위에 예시는 N = 3일 경우이다.

---

처음에는 BFS로 쉽게 구현하였다.

boolean[]visit = new boolean[n+1];
        Queue<Integer>q = new LinkedList<>();
        q.add(1);
        visit[1] = true;

        boolean check = false;
        while(!q.isEmpty()){
            int curNode = q.peek();
            q.remove();

            for(Integer i : gragh[curNode]){
                if(i != n && visit[i] == true){ //사이클이 생기는 구간
                    check=true;
                    break;
                }
                else if(i != n){
                    visit[i] = true;
                    q.add(i);
                }
            }
            if(check)break;
        }

다음에 탐색할 노드 번호가 N이 아니고 이전에 방문한적이 있다면 사이클이라고 생각해 boolean형 배열 check를 true로 설정하고

탈출하였다.

 

하지만 74%에서 계속 틀렸습니다.가 나왔다.

---

다시 생각해보면 현재 노드의 상태를 저장해주는것이다.

위에 그림을 보면 1번 노드 부터 탐색한다고 하자. 

visit[1] = -1

2번 노드는 더이상 탐색할 노드가 없으므로 

visit[2] = 1

3번 노드는 방문은 했지만 아직 재귀함수가 종료되지 않았다.

visit[3] = -1

현재 4번 노드는 1번 노드를 탐색하려고 한다.

하지만 visit[1] = -1 이다.

그렇게 되면 사이클이 생기게 되는 것이다.

이를 코드로 구현하자.

private static void dfs(int start){
        visit[start] = -1; //재귀 함수의 시작
        for(Integer i : gragh[start]){
            if(visit[i] == -1){ //방문은 했지만 아직 재귀함수를 돌고있는 노드
                check=true;
                return;
            }
            else{
                dfs(i);
            }
        }
        visit[start] = 1; //모두 탐색 완료
    }

이렇게 하면 사이클을 판별할 수 있다.

---

전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {
    private static List<Integer>[]gragh;
    private static int[] visit;
    private static int n;
    private static boolean check;
    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());
        gragh  = new List[n+1];
        for(int i=1;i<=n;i++)gragh[i] = new ArrayList<>();

        for(int i=1;i<=n-1;i++){
            st = new StringTokenizer(br.readLine());
            int edges = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            for(int j=0;j<edges;j++){
                gragh[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        visit = new int[n+1];
        check = false;

        dfs(1);


        if (check) {
            System.out.println("CYCLE");
        } else {
            System.out.println("NO CYCLE");
        }
    }
    private static void dfs(int start){
        visit[start] = -1;
        for(Integer i : gragh[start]){
            if(visit[i] == -1){
                check=true;
                return;
            }
            else{
                dfs(i);
            }
        }
        visit[start] = 1;
    }
}