2564 - 경비원 (Java)

 

---

 

문제

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

 

풀이

기본적으로 bfs, 그래프 탐색으로 문제를 접근했다.

 

우선 점 하나를 배열의 한 칸이라고 생각해서 2차원 배열을 선언해주었다.

해당 2차원 배열에는 좌표에 맞게 상점들을 위치 시킨다.

상점들의 숫자 번호를 그대로 사용해서 배열에 넣어주면 된다.

( 상점들의 위치는 항상 테두리에 위치하는데, 들어온 값에 따라 동서남북을 분기해주고,

  그 시작점에서 거리만큼 떨어진곳에 위치시켜주면 된다.)

 

상점들은 최대 100번까지 있기때문에 상점이 위치한곳 빼고는 모두 101을 넣어, 상점이 위치하지 않다고 표기한다.

 

방문 배열 같은 경우에는, 겉 테두리만 모두 방문하지 않게 선언한다.

2차원 배열이지만 실제적으로는 끝 라인들만 사용하기 때문이다.

 

최종적으로 시작점에서부터 bfs 탐색을 시작해서, 내가 현재 찾아야 하는

상점까지의 거리를 체크한다. bfs를 수행하므로 당연히 최단거리가 될것이다.

 

참고로, 상점을 찾을때마다 방문 배열은 초기화해주어야한다.

 

 

 

코드

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

public class Main {

    public class Point {
        public int xPos;
        public int yPos;

        public Point(int xPos, int yPos) {
            this.xPos = xPos;
            this.yPos = yPos;
        }
    }

    public void solution() throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int answer = 0;

        int storeCount = Integer.parseInt(br.readLine());

        int block[][] = new int[n + 1][m + 1];
        // 테두리 세팅
        for(int i=0; i<m+1; i++){
            block[0][i] = 101;
            block[n][i] = 101;
        }
        for(int i=0; i<n+1; i++) {
            block[i][0] = 101;
            block[i][m] = 101;
        }

        for (int i = 0; i < storeCount; i++) {
            st = new StringTokenizer(br.readLine());
            int direction = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());

            if(direction == 1) block[0][distance] = i+1; // 북쪽
            if(direction == 2) block[n][distance] = i+1;
            if(direction == 3) block[distance][0] = i+1;
            if(direction == 4) block[distance][m] = i+1;
        }

        st = new StringTokenizer(br.readLine());
        int direction = Integer.parseInt(st.nextToken());
        int distance = Integer.parseInt(st.nextToken());

        int startX = 0;
        int startY = 0;
        if(direction == 1) {
            startX = 0;
            startY = distance;
        }

        if(direction == 2){
            startX = n;
            startY = distance;
        }

        if(direction == 3) {
            startX = distance;
            startY = 0;
        }

        if (direction == 4) {
            startX = distance;
            startY = m;
        }


        // bfs
        for (int i = 0; i < storeCount; i++) {

            int dx[] = new int[]{0, 0, -1, 1};
            int dy[] = new int[]{1, -1, 0, 0};
            int moveArray[][] = new int[n+1][m+1];

            // 매번 복사.
            int tempBlock[][] = new int[n+1][m+1];
            for (int j = 0; j < n + 1; j++) {
                for (int k = 0; k < m + 1; k++) {
                    tempBlock[j][k] = block[j][k];
                }
            }

            Deque<Point> queue = new ArrayDeque<>();
            queue.addLast(new Point(startX, startY));
            tempBlock[startX][startY] = 0; // 방문 표시

            int targetNumber = i+1;

            while (!queue.isEmpty()) {
                Point point = queue.pollFirst();
                int xPos = point.xPos;
                int yPos = point.yPos;

                for (int j = 0; j < 4; j++) {
                    int nx = xPos + dx[j];
                    int ny = yPos + dy[j];

                    if(nx >= 0 && nx < n+1 && ny >= 0 && ny < m+1 && tempBlock[nx][ny] != 0){
                        queue.addLast(new Point(nx, ny));
                        moveArray[nx][ny] = moveArray[xPos][yPos] + 1;
                        if(tempBlock[nx][ny] == targetNumber) answer += moveArray[nx][ny];
                        tempBlock[nx][ny] = 0;
                    }
                }
            }
        }

        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

}

 

후기

 

생각나는대로 구현해서 코드가 길고 지저분,,