[백준/16724/Java] "피리 부는 사나이" 초간단 설명

Jake·2022년 3월 4일

Problem Solving

PS

목록 보기

4/14

1. 문제 이해

예시 1

예제 입력 1을 화살표로 그리면 위와 같습니다.

파란색 화살표들은 서로 순환하는 구조입니다.
빨간색 화살표들도 서로 순환하는 구조입니다.

따라서 위 예시에서는 파란색 화살표의 위치 중 하나, 그리고 빨간색 화살표의 위치 중 하나에 safe zone을 배치하면 모든 사람들이 safe zone에 들어갈 수 있게 됩니다.

예시 1의 정답은 2입니다.

예시 2

예시 1에서 (0, 3), (1, 3) 화살표의 방향을 바꾼 표입니다.

위 그림에서는 파란색이 서로 순환하는 구조는 아니기 때문에 (1, 3)에 safe zone을 두어야 합니다.
빨간색 화살표는 여전히 두 포인트 중 한 곳에 safe zone을 두면 됩니다
초록색 화살표는 같은 색 화살표와 이어지지 않음으로, (0, 3)에 safe zone을 배치하면 됩니다
예시 2의 정답은 3입니다.

2. 문제 해석

위 두 예시에서 알 수 있듯, 이 문제는 표에서 서로 연결된 화살표 그룹이 총 몇개 있는지 찾아내는 문제입니다.
순환하지 않는 화살표 그룹이라면 끝 화살표에, 순환하는 화살표 그룹이라면 그룹 내 아무 곳에나 safe zone을 배치하면 됩니다.

3. 코드

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

public class Main {

    static char[][] board;
    static int[][] markBoard;
    static int count;
    static int n, m;
    static final int nowTraversing = -1;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

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

        markAll();

        System.out.println(count);
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = pi(st.nextToken());
        m = pi(st.nextToken());

        board = new char[n][m];
        markBoard = new int[n][m];
        count = 0;
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = line.charAt(j);
            }
        }
    }

    private static void markAll() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (markBoard[i][j] == 0) {
                    markBoard[i][j] = traverse(i, j);
                }
            }
        }
    }

    static int traverse(int x, int y) {//dfs라고 보셔도 무방합니다
        if(!valid(x, y) || isLoop(x, y)) {
            return ++count;
        } else if(isMarked(x, y)) {
            return markBoard[x][y];
        } else {
            markBoard[x][y] = nowTraversing;

            int dir = getDir(board[x][y]);
            int nextX = x + dx[dir];
            int nextY = y + dy[dir];
            markBoard[x][y] = traverse(nextX, nextY);

            return markBoard[x][y];
        }
    }

    static boolean isLoop(int x, int y) {
        if (markBoard[x][y] == nowTraversing) {
            return true;
        } else return false;
    }

    static boolean valid(int x, int y) {
        if(x < 0 || x >= n || y < 0 || y >= m) return false;
        else return true;
    }

    static boolean isMarked(int x, int y) {
        if(markBoard[x][y] > 0) return true;
        else return false;
    }

    static int getDir(char c) {
        switch(c) {
            case 'U':
                return 0;
            case 'R':
                return 1;
            case 'D':
                return 2;
            case 'L':
                return 3;
            default:
                System.out.println("wrong character Input");
                return -1;
        }
    }

    public static int pi(String str) {
        return Integer.parseInt(str);
    }

}