[JAVA] BOJ21922 학부 연구생 민상

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 시뮬레이션

 

문제 풀이 방법

• 물건이 있을 때, 나아가야되는 방향이 바뀌는데 경우를 나누어서 에어컨 바람이 갈 수 있는 곳을 찾았습니다.
• 이 때, 한 번 갔던 곳이라고 해서 2차원 배열을 사용해서 방문 처리를 하면, 다시 못 가는 경우가 발생하게 됩니다.
  • 에어컨 바람은 교차해서 갈 수 있으므로 한 번 갔다고 해서 다시 못가게 된다면, 오답입니다.
  • 따라서 2차원 배열이 아닌, 3차원 배열을 사용했습니다.
• Wind클래스는 에어컨에서 나오는 바람에 대한 정보로, 현재 행, 열 번호와 나아가는 방향의 정보를 담아줬습니다.

 

코드

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

public class Main {
    static class Wind {
        int r, c, vr, vc;

        public Wind(int r, int c, int vr, int vc) {
            this.r = r;
            this.c = c;
            this.vr = vr;
            this.vc = vc;
        }
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M, map[][], dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
    static Queue<Wind> queue = new LinkedList<>();
    static boolean v[][];

    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        v = new boolean[N][M];

        for(int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for(int c = 0; c < M; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
                if(map[r][c] == 9) {
                    for(int d = 0; d < 4; d++) queue.add(new Wind(r, c, dr[d], dc[d]));
                }
            }
        }

        System.out.println(func());
    }

    private static int func() {
        int result = 0;
        boolean visit[][][] = new boolean[4][N][M];

        while(!queue.isEmpty()) {
            Wind current = queue.poll();

            int vr = current.vr;
            int vc = current.vc;

            if(!v[current.r][current.c]) {
                v[current.r][current.c] = true;
                result++;
            }

            visit[findIdx(vr, vc)][current.r][current.c] = true;

            if(map[current.r][current.c] == 1) vc *= -1;
            else if(map[current.r][current.c] == 2) vr *= -1;
            else if(map[current.r][current.c] == 3) {
                int tmp = vc;
                vc = -vr;
                vr = -tmp;
            } else if(map[current.r][current.c] == 4) {
                int tmp = vr;
                vr = vc;
                vc = tmp;
            }

            int nr = current.r + vr;
            int nc = current.c + vc;

            int idx = findIdx(vr, vc);
            if(!check(nr, nc) || visit[idx][nr][nc]) continue;

            visit[idx][nr][nc] = true;
            queue.add(new Wind(nr, nc, vr, vc));
        }
        return result;
    }

    private static int findIdx(int r, int c) {
        if(r == dr[0] && c == dc[0]) return 0;
        else if(r == dr[1] && c == dc[1]) return 1;
        else if(r == dr[2] && c == dc[2]) return 2;
        else  return 3;
    }

    private static boolean check(int nr, int nc) {
        return nr >= 0 && nr < N && nc >= 0 && nc < M;
    }
}

 

느낀점

아무리 테스트케이스를 만들고 해봐도 맞는 것 같은데, 계속 틀려서 헤맸습니다.

(질문을 올리니까 직접 문제 출제자 님이 답변해주셨다는,,,)

문제를 해결할 때, 잘 설계하고, 미쳐 생각하지 못한 부분이 있는지 꼼꼼하게 확인하는 습관을 길러야될 것 같습니다...

화이팅..ㅜ !!