[BOJ] 백준 16724 - 피리 부는 사나이 풀이

1. 문제

2. 풀이

• DFS를 이용하여 해결
• 각각의 배열 요소는 2가지 값을 가진다.
  • 배열에서의 자신의 위치 (=인덱스)
  • 방향
• 이를 이용하여 인접리스트를 구성할 수 있다.
• 방향에 따른 노드 번호 연결 방법
  • ↑ : 자신의 인덱스 - M
  • ↓ : 자신의 인덱스 + M
  • → : 자신의 인덱스 + 1
  • ← : 자신의 인덱스 - 1

• 주요 자료구조
  • boolean[] visited : DFS 방문 배열 
  • boolean[] isCycled : 처리 완료 배열
  • List<Integer>[] inList : 인접리스트
  • int result : 사이클이 생긴 횟수
• 노드를 연결했다면 0 ~ N - 1번 노드까지 처리 배열이 false라면 pipeDFS() 함수를 시작한다.
• pipeDFS()는 크게 다음과 같은 4가지 부분으로 나눌 수 있다.
  1. 지금 탐색하는 노드가 이미 방문한 노드라면
  2. 내 다음 노드가 처리된 노드라면
  3. 다음 노드로 재귀
  4. return을 만나고 돌아왔을 때 처리배열을 True로 처리하기
• 지금 탐색하는 노드가 이미 방문한 노드라면 2가지 경우가 있을 수 있다.
  1. 내 다음 노드가 방문은 했었는데 처리를 안 한 노드라면
     • 1번의 경우 내 다음 노드를 처리해준다음 result를 하나 증가시키고 return 한다.
  2. 내 다음 노드가 방문했던 노드고 처리를 한 노드라면
     • 이미 처리를 한 노드이므로 그냥 return한다
• 내 다음 노드가 처리된 노드라면 재귀를 타거나 다른 일을 할 필요 없이 return 시킨다.
• 위의 두 가지 상황에 걸리지 않는다면 현재 탐색하고 있는 노드를 방문처리 시킨 후 다음 노드로 재귀를 돌린다.
• 방금 돌린 재귀를 끝내고 돌아왔다는건 처리를 해주고 돌아왔거나 이미 처리된 노드를 만나도 돌아왔다는 이야기.
  • 따라서 지금 노드를 처리해준다.(isCycled를 true로 만든다.)

• 그 후 result를 출력하면 종료!!
  
  

3. 소스 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N; // 지도의 행 수
    static int M; // 지도의 열 수

    static int result = 0;
    static boolean[] visited; // DFS 방문 배열 
    static boolean[] isCycled; // 처리 완료 배열
    static List<Integer>[] inList; // 인접리스트

    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());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 인접리스트 만들기
        inList = new ArrayList[N * M];
        for (int i = 0; i < N * M; i++) {
            inList[i] = new ArrayList<>();
        }

        // 인접 리스트 초기화
        int idx = 0;
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                switch (input.charAt(j)) {
                    case 'U':
                        inList[idx].add(idx - M);
                        break;

                    case 'D':
                        inList[idx].add(idx + M);
                        break;

                    case 'L':
                        inList[idx].add(idx - 1);
                        break;

                    case 'R':
                        inList[idx].add(idx + 1);
                        break;
                }
                idx++;
            }
        }

        // 방문배열 초기화
        visited = new boolean[N * M];
        isCycled = new boolean[N * M];

        // DFS 함수 실행
        for (int i = 0; i < N * M; i++) {
            if (!isCycled[i]) {
                pipeDFS(i);
            }
        }

        //결과 출력
        bw.write(Long.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    // DFS 함수
    private static void pipeDFS(int idx) {
        // 이미 방문한 노드라면
        if (visited[idx]) {
            // 방문은 했는데 처리를 안해준 노드라면
            if (!isCycled[inList[idx].get(0)]) {
                isCycled[idx] = true;
                result++;
            }
            return;
        }

        // 내 다음 노드가 이미 처리된 노드라면
        if (isCycled[inList[idx].get(0)]) {
            return;
        }

        // 지금 현재 노드 방문처리
        visited[idx] = true;

        // 다음 노드로 DFS
        pipeDFS(inList[idx].get(0));

        // return을 만났다면 현재 노드를 처리
        isCycled[idx] = true;
    }
}

4. 점수

80 / 100