[백준] 21606번 : 아침 산책

아침 산책

---

풀이 방법

이번 문제는 다음과 같이 서브태스크 문제로 총 200점을 달성해야 해결되는 문제이다.
먼저 108점으로 실패한 풀이를 설명하고 200점으로 성공한 풀이를 설명하겠다..

틀린 방법

먼저 문제 예제를 먼저 살펴봤다.

1 - 3,4
3 - 1,4
4 - 1,3,5
5 - 4

이렇게 총 8개의 경우의 수가 나온다는 것을 알 수 있었다.

그래서 무작정 DFS를 돌려서 시작점이 실내인 경우만 모든 탐색을 해서 야외면 계속 탐색을 진행하고 실내를 만나면 count값을 증가시켜주면 된다.

물론 이건 틀린방법이다..

틀린 코드..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static List<List<Integer>> graph;
    static int[] inOut;
    static boolean[] visited;
    static int n;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        inOut = new int[n+1];

        graph = new ArrayList<>();
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<>());
        }

        String A = br.readLine();
        for(int i=1;i<n+1;i++){
            inOut[i] = Integer.parseInt(String.valueOf(A.charAt(i-1)));
        }

        for(int i=0;i<n-1;i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            graph.get(from).add(to);
            graph.get(to).add(from);
        }

        for(int i=1;i<=n;i++){
            visited = new boolean[n+1]; //각 정점마다 방문 초기화
            //시작이 실내이면
            if(inOut[i]==1) {
                dfs(i);
            }
        }

        System.out.println(count);
    }
    private static void dfs(int start) {
        visited[start] = true;

        for(int v : graph.get(start)){
            //중간에 모두 야외이며 마지막은 실내로 끝나야 함.
            //야외이면 계속 탐색. - 실내이면 count++
            if(!visited[v]){
                if(inOut[v]==0){
                    dfs(v);
                }
                else{
                    count++;
                }
            }
        }
    }
}

해결 방법

접근을 달리해서 실외를 기준으로 잡아야 한다.

실내 -> 실내로 갈수 있는 경로는 n(n-1)의 경우의 수가 생기게 된다.
그리고 실내가 인접해 있는 경우는 또 따로 계산해줘야 한다.

자세한건 다음 블로그를 참조하자.

참고 블로그
https://prodyou.tistory.com/16

느낀 점

골드 3 문제여서 내 손으로 직접 해결해서 기분이 좋았었는데, 정답이 아니였다..
탐색 문제더라도 탐색 시 시간 초과가 난다면 다른 방법을 생각해야 하는데 그게 쉽지않다..
이번 문제처럼 실내를 기준으로 탐색해서 정답이 아니라면 실외를 기준으로 찾는 즉, 반대로 접하는 방법을 한번 생각해 보기를 기억하자!
더 많은 문제를 접해봐야겠다.!!

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static List<List<Integer>> graph;
    static int[] inOut;
    static boolean[] visited;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        inOut = new int[n+1];
        int route_count = 0;

        graph = new ArrayList<>();
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<>());
        }

        String A = br.readLine();
        for(int i=1;i<n+1;i++){
            inOut[i] = Integer.parseInt(String.valueOf(A.charAt(i-1)));
        }

        for(int i=0;i<n-1;i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            graph.get(from).add(to);
            graph.get(to).add(from);

            if(inOut[from]==1 && inOut[to]==1){ //실내끼리 인접하면 경로를 2개 더함
                route_count += 2;
            }
        }

        visited = new boolean[n+1];
        for(int i=1;i<=n;i++){
            int in = 0; //실내의 수
            if(inOut[i]==0) { 
                if(!visited[i]){
                    visited[i] = true;
                    in = dfs(i); //실외를 만나면 탐색
                }
            }
            route_count += in*(in-1); //실내(실내-1)
        }

        System.out.println(route_count);
    }
    private static int dfs(int start) {
        int in = 0;

        for(int v : graph.get(start)){
            if(inOut[v]==0){ 
                if(!visited[v]) {
                    visited[v] = true;
                    in += dfs(v); //실외면 계속 탐색
                }
            }
            else{ //실내라면
                in++;
            }
        }
        return in;
    }
}