백준 17290번 Crazy_aRcade_Good JAVA

링크텍스트

설명

풀이 흐름 설명

처음에는 단순히 Arrays.fill()을 이용하여 폭탄이 존재하는 행을 전부 채우는 방식으로 해결하려고 했다. 폭탄이 하나라도 존재하는 행은 모두 위험하다고 판단했기 때문이다.

그러나 이 방식은 치명적인 문제가 있었다.
행 단위로만 처리를 하면 열에 존재하는 폭탄의 영향을 반영할 수 없었고
또한 한 행에 여러 개의 폭탄이 존재하는 경우 다른 열로 퍼지는 위험 영역을 정확히 처리할 수 없다는 점을 깨달았다.

문제를 다시 정리해보니 폭탄이 (i, j)에 존재한다면
해당 행 전체와 해당 열 전체가 위험 영역이 된다는 사실을 알 수 있었다.

따라서 특정 칸 (x, y)이 안전하려면 그 행 x에 폭탄이 하나도 없어야 하고
그 열 y에도 폭탄이 하나도 없어야 한다는 조건을 도출하였다.

이후 모든 칸(10×10)을 완전 탐색하면서 각 칸이 안전한지 직접 검사하였다.
안전한 칸이라면 시작 위치 (r, c)와의 맨해튼 거리
|r - i| + |c - j|를 계산하여 최소값을 갱신하였다.

장애물이 존재하지 않기 때문에 최단 거리는 항상 맨해튼 거리와 같으며,
따라서 BFS 없이도 해결할 수 있다고 판단하였다.

고민과 해결

처음에는 BFS를 사용하여 최단 거리를 구하려고 하였다.
격자 형태의 이동 문제였기 때문에 자연스럽게 BFS를 떠올렸다.

그러나 다시 생각해보니 이 문제에는 이동을 막는 장애물이 존재하지 않았다.
폭탄 위를 지나가는 것도 허용되며
단지 최종 위치가 안전한지만 판단하면 되는 문제였다.

즉 경로 탐색 문제가 아니라
“어떤 점이 위험 직선 위에 속하는가”를 판단하는 기하학적 문제였다.

이 사실을 깨닫고 나서는 굳이 BFS로 모든 칸을 탐색할 필요 없이
모든 좌표를 직접 확인한 뒤 맨해튼 거리의 최솟값을 구하는 방식으로 단순화하였다.

문제를 이동 문제로 바라봤을 때는 복잡해 보였지만
좌표 평면에서 직선의 합집합을 제외하는 문제로 해석하니 구조가 명확해졌다.
시간복잡도: BFS 코드 기준 O(N³), 공간복잡도: O(N²)

회독

• [ x ] 1회
• 2회
• 3회

처음 코드

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

public class Main {
        static char [][] arr;
        static int [] dx = {-1,1,0,0};
        static int [] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        arr = new char[11][11];

        for(int i=1;i<=10;i++){
            String s = br.readLine();
            for(int j=1;j<=10;j++){
                arr[i][j] = s.charAt(j-1);
            }
        }

        bfs(r, c);
    }

    public static void bfs(int r, int c){
        Queue<int []> q = new LinkedList<>();
        boolean [][] check = new boolean[11][11];

        q.offer(new int[]{r,c,0});
        check[r][c] = true;

        while(!q.isEmpty()){
            int [] now = q.poll();

            int x = now[0];
            int y = now[1];
            int count = now[2];

            boolean safe = true;

            // 열 검사
            for(int i=1;i<=10;i++){
                if(arr[i][y]=='o'){
                    safe = false;
                    break;
                }
            }

            // 행 검사
            for(int j=1;j<=10;j++){
                if(arr[x][j]=='o'){
                    safe = false;
                    break;
                }
            }

            if(safe){
                System.out.println(count);
                return;
            }

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

                if(nx<1 || nx>10 || ny<1 || ny>10 || check[nx][ny]) continue;

                check[nx][ny] = true;
                q.offer(new int[]{nx,ny,count+1});
            }
        }
    }
}

최종 코드

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

public class Main {

    static char[][] arr = new char[11][11];

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        for(int i=1;i<=10;i++){
            String s = br.readLine();
            for(int j=1;j<=10;j++){
                arr[i][j] = s.charAt(j-1);
            }
        }

        int answer = Integer.MAX_VALUE;

        // 모든 칸 탐색 (100칸)
        for(int i=1;i<=10;i++){
            for(int j=1;j<=10;j++){

                boolean safe = true;

                // 행 검사
                for(int k=1;k<=10;k++){
                    if(arr[i][k] == 'o'){
                        safe = false;
                        break;
                    }
                }

                // 열 검사
                if(safe){
                    for(int k=1;k<=10;k++){
                        if(arr[k][j] == 'o'){
                            safe = false;
                            break;
                        }
                    }
                }

                // 안전한 칸이면 거리 계산
                if(safe){
                    int dist = Math.abs(r - i) + Math.abs(c - j);
                    answer = Math.min(answer, dist);
                }
            }
        }

        System.out.println(answer);
    }
}