BOJ) Crazy_aRcade_Good (크레이지 아케이드)

Crazy_aRcade_Good

17290번: Crazy_aRcade_Good

풀이

 

맵을 돌면서 안전 구역을 찾는 기본적인 구현 문제다. 

조금 더 수월하게 풀기 위해, 입력받은 map을 char[][]로 저장해주었다.

또한, Bazzi 클래스를 만들어서 좌표와 걸음 수를 저장했다. (넥슨 캐릭터 중에 제일 귀여워서 배찌로 클래스를 만들었다...) 

이후, 처음 입력받은 위치 좌표를 Bazzi에 담아 큐에 담고 우선순위 큐에 담아 맵을 탐색한다. (탐색은 상하좌우 4방향)

visit을 통해 여러번 체크하는 것을 방지해주었다. 

맵 크기가 10으로 고정되어 있기 때문에, dfs로 풀어도 충분히 풀 수 있을거라고 생각한다.

 

오늘 백준 문제를 풀면서 결과를 보니까, 예전에 풀었을 때보다 성장한 것을 느낄 수 있었다.

프로그래머스는 매일같이 풀면서 별로 체감이 안났는데, 많이 성장했다.

조금 더 힘내자!

 

코드

 

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

public class CrazyArcade_17290 {
    final static int[] dx = {1,0,-1,0}, dy = {0,1,0,-1};
    final static int SIZE = 10;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //r : y, c : x
        String[] strArr = br.readLine().split(" ");
        int[] pos = {Integer.parseInt(strArr[0])-1, Integer.parseInt(strArr[1])-1};
        char[][] map = new char[SIZE][SIZE];

        for(int i=0; i<SIZE; i++) {
            map[i] = br.readLine().toCharArray();
        }

        System.out.println(solution(pos, map));

        br.close();
    }

    private static int solution(int[] pos, char[][] map) {
        int answer =0;

        PriorityQueue<Bazzi> pq = new PriorityQueue<>();
        pq.offer(new Bazzi(pos[1], pos[0],0)); // (y,x)

        int[][] visit = new int[SIZE][SIZE];
        visit[pos[0]][pos[1]] = 1; // (y,x)
        while(!pq.isEmpty()) {
            Bazzi bazzi = pq.poll();

            if(isSafe(bazzi, map)) {
                answer = bazzi.step;
                break;
            }

            for(int i=0; i<4; i++) {
                int ny = bazzi.y + dy[i];
                int nx = bazzi.x + dx[i];

                if(isInArea(nx,ny)) {
                    if(visit[ny][nx] ==0) {
                        visit[ny][nx] =1;
                        int step = bazzi.step+1;
                        pq.offer(new Bazzi(nx,ny, step));
                    }
                }
            }
        }
        return answer;
    }

    private static boolean isInArea(int nx, int ny) {
        return nx >=0 && nx <SIZE && ny >=0 && ny <SIZE ? true : false;
    }

    private static boolean isSafe(Bazzi bazzi, char[][] map) {
        for(int i=0; i<SIZE; i++) {
            if(map[i][bazzi.x] == 'o') {
                return false;
            }
        }
        for(int i=0; i<SIZE; i++) {
            if(map[bazzi.y][i] == 'o') {
                return false;
            }
        }
        return true;
    }
}

class Bazzi implements Comparable<Bazzi>{
    int x;
    int y;
    int step;

    public Bazzi(int x, int y, int step) {
        this.x = x;
        this.y = y;
        this.step =step;
    }

    @Override
    public int compareTo(Bazzi b) {
        return this.step > b.step ? 1: -1;
    }
}