백준 21922(학부 연구생 민상) - java

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

21922번: 학부 연구생 민상

 

문제

학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다.

연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 4방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다.

민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다.

연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다.

연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다.

 

연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다.

민상이가 원하는 자리는 몇 개 있는지 계산해주자.

 

유형 : DFS + 구현

 

접근 방식

• 각 격자에 맞게 방향을 바꿀 수 있게 메소드를 만든다.
• 방문 배열을 3차원으로 설정한다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;

    static int m = 0;

    static int[][] board;

    // U - R - D - L

    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};

    static boolean[][][] v;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n+1][m+1];
        v = new boolean[n+1][m+1][4];


        for(int i=1;i<=n;i++){
            st = new StringTokenizer(bf.readLine()," ");

            for(int j=1;j<=m;j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){

                if(board[i][j] == 9){
                    for(int k=0;k<4;k++){
                        v[i][j][k] = true;
                        move(i,j,k);
                    }
                }

            }
        }

        int count = 0;
        for(int i=1;i<=n;i++) {
            for (int j = 1; j <= m; j++) {
                if(v[i][j][0] || v[i][j][1] || v[i][j][2] || v[i][j][3]){
                    count += 1;
                }
            }
        }

        System.out.println(count);
        bf.close();
    }

    static void move(int x,int y,int dir){

        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if(nx < 1 || nx > n || ny < 1 || ny > m)
            return;


        if(board[nx][ny] == 1){
            dir = first(dir);

            if(v[nx][ny][dir]){
                return;
            }

            v[nx][ny][dir] = true;
        }else if(board[nx][ny] == 2){
            dir = second(dir);

            if(v[nx][ny][dir]){
                return;
            }

            v[nx][ny][dir] = true;
        }else if(board[nx][ny] == 3){
            dir = third(dir);

            if(v[nx][ny][dir]){
                return;
            }

            v[nx][ny][dir] = true;
        }else if(board[nx][ny] == 4){
            dir = four(dir);

            if(v[nx][ny][dir]){
                return;
            }

            v[nx][ny][dir] = true;
        }else if(board[nx][ny] == 0){

            if(v[nx][ny][dir]){
                return;
            }
            
            v[nx][ny][dir] = true;
        }

        move(nx,ny,dir);
    }

    // U - R - D - L

    static int first(int dir){

        if(dir == 0 || dir == 2)
            return dir;

        if(dir == 1)
            return 3;

        return 1;
    }

    // U - R - D - L

    static int second(int dir){

        if(dir == 1 || dir == 3)
            return dir;

        if(dir == 0)
            return 2;

        return 0;
    }

    // U - R - D - L

    static int third(int dir){
        if(dir == 0){
            return 1;
        }else if(dir == 1){
            return 0;
        }else if(dir == 2){
            return 3;
        }
        return 2;
    }

    // U - R - D - L

    static int four(int dir){
        if(dir == 0){
            return 3;
        }else if(dir == 1){
            return 2;
        }else if(dir == 2){
            return 1;
        }
        return 0;
    }
}