[Java] 술래잡기

✔ 술래잡기

[코드트리 술래잡기]

문제 분석하기

술래와의 거리가 3 이하인 도망자를 찾아 이동시키고, 술래도 이동한 후 시야 내에 있는 도망자를 잡아 점수를 얻게 됨

만약 나무가 놓여 있는 칸이라면 해당 칸에 도망자가 있어도 나무에 가려져 보이지 않는 것으로 함 

술래가 K번의 턴 동안 얻게 되는 총 점수를 출력하도록 함

 

 

손으로 풀어보기

1. 격자의 크기 N 저장
2. 도망자의 수 M 저장
3. 나무의 수 H 저장
4. 턴의 수 K 저장
5. 도망자의 위치와 이동 방법(1 - 좌우, 2 - 상하) 저장
6. 나무의 위치를 저장
7. K번의 턴 동안 술래 잡기
   1. 술래와의 거리가 3 이하인 도망자 찾기
   2. 도망자는 바라 보고 있는 방향으로 1칸 움직이며 이때 움직이려는 칸에 술래가 있다면 움직이지 않음
      만약 격자를 벗어난다면 방향을 반대로 틀어 1칸 움직이며 이때 움직이려는 칸에 술래가 있다면 움직이지 않음
   3. 술래는 달팽이 모양으로 움직이며, 만약 이동방향이 틀어지는 지점이라면 방향을 바로 틀어주도록 함
      
      • 달팽이 모양으로 움직이기 위해서는
        상우하좌 방향으로 1, 2, 3, 4, ... 씩의 길이로 증가하며 2번씩 반복하여 이동하도록 해야 함
      • 예) 순방향
        상 1만큼 이동, 우 1만큼 이동
        하 2만큼 이동, 좌 2만큼 이동
        상 3만큼 이동, 우 3만큼 이동
        하 4만큼 이동, 좌 4만큼 이동
        (1행, 1열) 도달
      • 예) 역방향
        하 4만큼 이동, 우 4만큼 이동
        상 3만큼 이동, 좌 3만큼 이동
        하 2만큼 이동, 우 2만큼 이동
        상 1만큼 이동, 좌 1만큼 이동
        정중앙 도달
      • 순방향의 경우, 상-우, 우-하, 하-좌, 좌-상으로 방향을 틀어줘야 함
      • 역방향의 경우, 하-우, 우-상, 상-좌, 좌-하로 방향을 틀어줘야 함
   4. 시야 내(현재 바라보고 있는 방향을 기준으로 현재 칸을 포함하여 총 3칸)에 있는 도망자를 잡도록 함
      만약 나무가 놓여 있는 칸이라면 넘어가도록 함
   5. 현재 턴을 t번째 턴이라고 했을 때 t * 현재 턴에서 잡힌 도망자의 수만큼의 점수를 얻게 됨
8. 술래가 얻게 되는 총 점수를 출력

슈도코드 작성하기

Point(좌표 정보를 나타내는 클래스) {
    containTree(나무 존재 여부)
    hiders(좌표에 위치하는 도망자들)
}

Person(사람 정보를 나타내는 클래스) {
    id(사람 순번)
    r, c(사람 위치)
    d(이동 방향)
}

술래잡기 준비 {
    N(격자의 크기)
    M(도망자의 수)
    H(나무의 수)
    K(턴의 수)
    
    도망자의 위치와 이동 방법 저장
    나무의 위치를 저장
    술래 저장
}

술래잡기 {
    for(K만큼) {
        도망자 이동하기
        술래 이동하기
        도망자 잡기
    }
}

술래잡기 결과 출력 {
    술래가 얻게 되는 총 점수 출력
}

Main {
    술래잡기 준비
    술래잡기
    술래잡기 결과 출력
}

코드 구현하기

/*
 * 술래잡기
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, M, H, K;
    static Point[][] board;
    static Person seeker;
    static Person[] hiders;
    static boolean opposite = false; // 술래 이동 방향 (true - 역방향, false - 순방향)
    static int seekerLength; // seekerLength(달팽이 모양의 한 획에서 술래가 현재 이동한 길이)
    static int seekerCount; // seekerCount(현재 길이에 대한 이동 횟수)
    static int moveLength = 1; // moveLength(달팽이 모양의 한 획에서 이동해야 하는 길이)
    static int[] dr = { -1, 0, 1, 0 }; // dr, dc(상, 우, 하, 좌 좌표)
    static int[] dc = { 0, 1, 0, -1 };
    static int answer;

    /*
     * Point(좌표 정보를 나타내는 클래스)
     */
    static class Point {
        boolean containTree; // containTree(나무 존재 여부)
        List<Person> hiders = new ArrayList<>(); // hiders(좌표에 위치하는 도망자들)

        public Point() {
            this.containTree = false;
        }
    }

    /*
     * Person(사람 정보를 나타내는 클래스)
     */
    static class Person {
        int id; // id(사람 순번)
        int r, c; // r, c(사람 위치)
        int d; // d(이동 방향)

        public Person(int id, int r, int c, int d) {
            this.id = id;
            this.r = r;
            this.c = c;
            this.d = d;
        }

        public void changeHiderDirection() { // 도망자 이동 방향 변경
            this.d = (this.d + 2) % 4;
        }
    }

    /*
     * 술래잡기 준비
     */
    static void init(StringTokenizer st) throws IOException {
        N = Integer.parseInt(st.nextToken()); // N(격자의 크기)
        M = Integer.parseInt(st.nextToken()); // M(도망자의 수)
        H = Integer.parseInt(st.nextToken()); // H(나무의 수)
        K = Integer.parseInt(st.nextToken()); // K(턴의 수)

        board = new Point[N][N]; // board(격자의 정보)
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                board[i][j] = new Point();
            }
        }

        hiders = new Person[M]; // hiders(도망자들 저장 배열)
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            int d = Integer.parseInt(st.nextToken());
            Person hider = new Person(i, x, y, d); // 도망자의 위치와 이동 방법 저장
            hiders[i] = hider;
            board[x][y].hiders.add(hider);
        }

        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            board[x][y].containTree = true; // 나무의 위치를 저장
        }

        seeker = new Person(0, (N - 1) / 2, (N - 1) / 2, 0); // 술래 저장
        seekerLength = 0;
        seekerCount = 0;
    }

    /*
     * 술래잡기
     */
    static void move() {
        for (int i = 0; i < K; i++) {
            moveHiders(); // 도망자 이동하기
            moveSeeker(); // 술래 이동하기
            catchHiders(i + 1); // 도망자 잡기
        }
    }

    /*
     * 이동할 수 있는 도망자 이동하기
     */
    static void moveHiders() {
        for (int i = 0; i < M; i++) {
            Person hider = hiders[i];
            if (hider == null) {
                continue;
            }
            if (canMove(hider)) { // 이동할 수 있는 도망자라면
                int nr = hider.r + dr[hider.d];
                int nc = hider.c + dc[hider.d];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                    hider.changeHiderDirection(); // 격자를 벗어나는 경우, 방향을 바꿔 이동
                    nr = hider.r + dr[hider.d];
                    nc = hider.c + dc[hider.d];
                }
                if (nr == seeker.r && nc == seeker.c) {
                    continue; // 술래가 있는 경우, 움직이지 않음
                }
                board[hider.r][hider.c].hiders.remove(hider); // 해당 칸으로 이동
                hider.r = nr;
                hider.c = nc;
                board[hider.r][hider.c].hiders.add(hider);
            }
        }
    }

    /*
     * 도망자 이동 가능 여부
     */
    static boolean canMove(Person hider) {
        int distance = Math.abs(hider.r - seeker.r) + Math.abs(hider.c - seeker.c);
        if (distance <= 3) { // 현재 술래와의 거리가 3 이하인 도망자만 움직임
            return true;
        }
        return false;
    }

    /*
     * 술래 이동하기
     */
    static void moveSeeker() {
        int nr = seeker.r + dr[seeker.d]; // nr, nc(술래가 이동할 다음 방향)
        int nc = seeker.c + dc[seeker.d];
        seekerLength++;

        if (seekerLength == moveLength) { // 달팽이 모양의 한 획에서 현재 술래가 이동할 거리를 모두 이동했다면
            seekerLength = 0;
            seekerCount++;
            if (!opposite) { // 순방향일 때 이동 방향 틀어주기
                if (seeker.d == 3) {
                    seeker.d = 0; // 좌 방향이었다면 상 방향으로 틀어주기
                } else {
                    seeker.d++; // 상, 우, 하 방향이었다면, 우, 하, 좌 방향으로 틀어주기
                }
            } else { // 역방향일 때의 이동 방향으로 틀어주기
                if (seeker.d == 0) {
                    seeker.d = 3; // 상 방향이었다면 좌 방향으로 틀어주기
                } else {
                    seeker.d--; // 우, 하, 좌 방향이었다면, 상, 우, 좌 방향으로 틀어주기
                }
            }
            if (seekerCount == 2) { // 현재 길이로 2번 이동했다면
                seekerCount = 0;
                if (!opposite) { // 순방향이라면, 달팽이 모양의 한 획에서 이동해야 하는 길이 1 증가
                    moveLength++;
                } else { // 역방향이라면, 달팽이 모양의 한 획에서 이동해야 히는 길이 1 감소
                    moveLength--;
                }
            }
        }

        if (nr == 0 && nc == 0) { // 양끝(1행, 1열)에 도달한다면
            opposite = true; // 역방향으로 전환
            moveLength = N - 1;
            seeker.d = 2; // 하 방향부터 시작
            seekerCount = -1;
            seekerLength = 0;
        } else if (nr == (N - 1) / 2 && nc == (N - 1) / 2) { // 정중앙에 도달한다면
            opposite = false; // 순방향으로 전환
            moveLength = 1;
            seeker.d = 0; // 상 방향부터 시작
            seekerCount = 0;
            seekerLength = 0;
        }

        seeker.r = nr;
        seeker.c = nc;
    }

    /*
     * 도망자를 잡아 점수 획득
     */
    static void catchHiders(int turn) {
        int count = 0;
        for (int i = 0; i < 3; i++) {
            int nr = seeker.r + dr[seeker.d] * i; // nr, nc(도망자를 잡을 위치)
            int nc = seeker.c + dc[seeker.d] * i;
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) { // 격자를 벗어났다면 넘어감
                continue;
            }
            Point point = board[nr][nc];
            if (point.containTree) { // 만약 나무가 놓여 있는 칸이라면 넘어감
                continue;
            }
            if (!point.hiders.isEmpty()) { // 도망자가 있을 경우 도망자를 잡음
                count += point.hiders.size();
                for (Person hider : point.hiders) { // 도망자 삭제
                    hiders[hider.id] = null;
                }
                point.hiders = new ArrayList<>();
            }
        }
        answer += (turn * count); // 현재 턴에서 잡힌 도망자의 수만큼의 점수 추가
    }

    /*
     * 술래잡기 결과 출력
     */
    static void print() {
        System.out.println(answer); // 술래가 얻게 되는 총 점수 출력
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        init(st);
        move();
        print();
    }
}