[백준] 21922번 - 학부 연구생 민상 (Java/자바)

 

21922번: 학부 연구생 민상

 

 

학부 연구생 민상

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	772	204	125	24.131%

 

 

문제

학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다.
연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 4방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다.
민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다.
연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다.
연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다.

 

물건 종류	물건 모양	바람의 이동 방향
물건 1
물건 2
물건 3
물건 4

연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다.
민상이가 원하는 자리는 몇 개 있는지 계산해주자.

 

입력

첫 번째 줄에는 연구실의 크기가 세로 N(1 <= N <= 2,000), 가로 M(1 <= M <= 2,000),  순으로 주어진다.
두 번째 줄부터 N + 1 줄까지 연구실 내부 구조 정보를 알려주는 값 M개가 주어진다.
 1,2,3,4는 위에서 설명한 물건의 종류이다.
 9는 에어컨을 의미하고, 0은 빈 공간을 의미한다.
에어컨은 0개 이상 50개 이하가 들어온다.

 

출력

민상이가 원하는 자리의 개수를 출력한다.

 

예제 입력 및 출력

예제 입력	예제 출력
8 8 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 4 0 1 0 0 3 0 0 3 0 0 0 0 0 0 1 0 0 1 0 9 0 0 4 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0	25

기타 테스트 케이스는 사이트에 있습니다.

 

---

문제 접근 방법

 

단순히 방문하기만 하면 되는 문제였다. 

전체적인 흐름은 너비우선탐색(BFS)와 유사하게 흐르도록 설정했다. 

※참고. 첫 구현시 BFS처럼 큐를 사용하는 것이 아닌 재귀로 풀었다.

이때 78%에서 시간초과가 발생했고 queue로 바꾸어 보니 정상 작동함

 

우선 Info라는 row, col 좌표와, 바람이 들어오는 방향 dirt이 담긴 class를 정의해 주었다.

이후 <Info>형식의 queue를 정의해주었고, input 방향과 ouput 방향이 헷갈릴 수 있기 떄문에

from_ / to_ 로 나누어 특정 숫자(식별하기 위한 식별자)를 할당해 주었다

전체 좌석위치는 int 형식의 2차원 map 배열에 할당하였으며,

앉을 수 있는 자리가 중복 count 되지 않기 위해 map과 똑같은 크기의 hasAir의 2차원 boolean 배열을 할당했다.

 

자세한건 아래 코드로 확인하자

 

이해 안되는 부분이 있거나 설명이 잘못된 부분이 있다면 언제든 댓글을 남겨주세요!

---

소스코드

package Study;

import java.io.*;
import java.util.*;

public class BJ_G21922{ 
    //방향 식별을 쉽게 하기 위해 선언
    final static int fromUp= -1;
    final static int toDown= -1;

    final static int fromDown = 1;
    final static int toUp = 1;

    final static int fromLeft = -2;
    final static int toRight = -2;

    final static int fromRight= 2;
    final static int toLeft = 2;
    
    //좌석의 정보를 담을 Info class
    static class Info{
        int row, col, dirt;
        public Info(int row, int col,int dirt){
            this.row = row;
            this.col = col;
            this.dirt = dirt;
        }
    }

    //기타
    static int N;
    static int M;
    static int[][] map;
    static boolean[][] hasAir;
    static int count;

    static Queue<Info> q = new LinkedList<>();

    //solver 함수
    static void solver(){
        //q 사용
        while(!q.isEmpty()){
            Info info = q.poll();
            int n = info.row;
            int m = info.col;
            int dirt = info.dirt;

            if(n<0 || m<0 || n>=N || m>=M){
                continue;
            }
            if(!hasAir[n][m]) count++;
            hasAir[n][m] = true;
            switch(map[n][m]){
                case 0:
                    if(dirt == fromUp)      q.add(new Info(n+1,m,toDown));
                    if(dirt == fromDown)    q.add(new Info(n-1,m,toUp));
                    if(dirt == fromRight)   q.add(new Info(n,m-1,toLeft));
                    if(dirt == fromLeft)    q.add(new Info(n,m+1,toRight));
                    break;
                case 1:
                    if(dirt == fromUp)      q.add(new Info(n+1,m,toDown));
                    if(dirt == fromDown)    q.add(new Info(n-1,m,toUp));
                    break;
                case 2:
                    if(dirt == fromRight)   q.add(new Info(n,m-1,toLeft));
                    if(dirt == fromLeft)    q.add(new Info(n,m+1,toRight));
                    break;
                case 3:
                    if(dirt == fromUp)      q.add(new Info(n,m-1,toLeft));
                    if(dirt == fromDown)    q.add(new Info(n,m+1,toRight));
                    if(dirt == fromRight)   q.add(new Info(n+1,m,toDown));
                    if(dirt == fromLeft)    q.add(new Info(n-1,m,toUp));
                    break;
                case 4:
                    if(dirt == fromUp)      q.add(new Info(n,m+1,toRight));
                    if(dirt == fromDown)    q.add(new Info(n,m-1,toLeft));
                    if(dirt == fromRight)   q.add(new Info(n-1,m,toUp));
                    if(dirt == fromLeft)    q.add(new Info(n+1,m,toDown));
                    break;
                default:
                    break;
            }
        }
    }
    
    //메인함수
    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());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        hasAir = new boolean[N][M];
        count = 0;
        //map 저장
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] ==9){ //에어컨이 존재하는 자리라면
                    //상하좌우 q에 넣음
                    q.add(new Info(i,j-1,toLeft));
                    q.add(new Info(i,j+1,toRight));
                    q.add(new Info(i-1,j,toUp));
                    q.add(new Info(i+1,j,toDown));
                    hasAir[i][j] = true;
                    count++;
                }
            }
        }
        solver();
        System.out.println(count);
    }
}