[Codetree Java] 꼬리잡기놀이

문제 링크

https://www.codetree.ai/training-field/frequent-problems/tail-catch-play/description?page=3&pageSize=20&username=nnindd&discussionRowsPerPage=5&discussionPage=1

접근 방법

큰 순서는 아래와 같다.

• 1의 위치를 리스트에 저장
• k번 게임 실행
  • 이동 (M만큼 for)
    • 바뀐 1의 위치 갱신
  • 공 던지는 4분면, 행, 열, 방향 구하기
  • 공 던지기
    • 맞음
      • 맞았다면 몇번째 사람인지 구하기
        • 맵의 크기만큼 반복문 돌면서 1인 곳 찾기
        • 1이면 해당 팀원 위치 리스트 받아오기
        • 그 리스트에 맞은 사람 위치 있는지 확인
        • 있으면 맵에서 1, 3 변경
        • 있으면 머리 리스트에서 1 위치 갱신
        • 인덱스 제곱 계산해서 반환
    • 안 맞음
      • 공 멈추기 않고 던지기

길다..
우욱..
깔끔하게 작성하려고 함수를 다 빼면서 작성하다가 헷갈려서 생각나는대로 적었다.
input이 적기 때문에 전부 확인해봐도 되었고, 시간복잡도는 O(K*N^2)라니 1000*20^2면.. 할만함

 

어려웠던 부분

공 던지는 위치를 구하는게 어려웠다.

일정한 크기에 대해서 지정을 하려면 % 연산이 필요하다는걸 알겠는데 어떻게 계산을 해야 할지 몰라서 처음엔 풀지 못했다.

일단 4분면 중 한곳에 위치할 수 있게 하고, 방향에 따라서 N 안에서 어디에 위치하는지...

/ 와 % 를 사용하면 된다는걸 아는데.. 아는데! 항상 헷갈린다..

더 많이 풀어봐야함

 

지나갈 수 있는 길이 1 2 2 3 4 4 4 이런 형식이 아니라 1 2 2 2 2 3 으로 끝나는 경우를 생각해봐야 한다.

1이 이동할 땐 4인 곳으로 가는 것이 아니라 2가 아닌 곳으로 간다고 생각해야 한다.

이 생각을 듣고 아득해짐......

코드

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

public class Main {

    static int N, M, K, map[][], total;
    static ArrayList<int[]> first; //1의 위치
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

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

        StringTokenizer tokens = new StringTokenizer(br.readLine());
        N = Integer.parseInt(tokens.nextToken()); //격자 크기
        M = Integer.parseInt(tokens.nextToken()); //팀의 개수
        K = Integer.parseInt(tokens.nextToken()); //라운드 수

        map = new int[N][N]; //맵
        total = 0;

        first = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
                if (map[i][j] == 1) { //1의 위치 저장
                    first.add(new int[]{i, j});
                }
            }
        }//end input

        for (int i = 0; i < K; i++) {
            total += play(i);
        }

        bw.write(total + "");
        bw.flush();
        bw.close();
    }

    private static int play(int k) {
        //이동
        for (int i = 0; i < M; i++) {
            int[] cur = move(first.get(i));
            //바뀐 1의 위치 갱신해주기
            first.set(i, cur);
        }

        //공던짐
        int[] rcd = getRowColDirection(k);
        int area = rcd[0];
        int row = rcd[1];
        int col = rcd[2];
        int d = rcd[3];

        int x = row;
        int y = col;
        int temp = 0;
        while (isRange(x, y)) { //범위 안 벗어날때까지
            if (map[x][y] != 0 && map[x][y] != 4) {
                //맞은 사람 몇번째인지 구하기 + 점수 갱신 + 머리 꼬리 바꾸기
                temp = checkIndex(x, y);
                break;
            }
            //안 맞았으면 다음방향
            x += dir[d][0];
            y += dir[d][1];
        }
        return temp;
    }

    private static int checkIndex(int x, int y) {
        //몇번째 사람인지 구하기

        ArrayList<int[]> list;

        //1인 부분 확인
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] != 1) continue;

                //이 팀원 리스트 불러옴
                list = getTeamPosition(new int[]{i, j});

                //이 팀원 중 이사람이 있는지 확인
                for (int k = 0; k < list.size(); k++) {
                    if (list.get(k)[0] == x && list.get(k)[1] == y) {
                        //머리 꼬리 맵에서 바꾸기
                        int[] front = list.get(0);
                        int[] back = list.get(list.size()-1);
                        int temp = map[front[0]][front[1]];
                        map[front[0]][front[1]] = map[back[0]][back[1]];
                        map[back[0]][back[1]] = temp;

                        //머리 리스트에 머리 변경
                        for (int l = 0; l < first.size(); l++) {
                            int[] head = first.get(l);
                            if(head[0] == front[0] && head[1] == front[1]){
                                first.set(l, back); //꼬리를 머리로 바꿈
                            }
                        }
                        //점수 반환
                        return (k + 1) * (k + 1);
                    }
                }
            }
        }
        return 0;
    }

    private static int[] getRowColDirection(int k) {
        //던진 위치에 따라서 행, 열, 방향을 구함
        // 좌 하 우 상 순서로 0 1 2 3
        int area, row, col, dir; //4변 중 위치, 어느 행/열에 있는지, 공던지는 방향

        area = (k / N) % 4; //4변 중 어디인지 구하기

        if (area == 0) {
            col = 0;
            row = k % N;
            dir = 3;
        } else if (area == 1) {
            row = N - 1;
            col = k % N;
            dir = 0;
        } else if (area == 2) {
            row = N - (k % N) - 1;
            col = N - 1;
            dir = 2;
        } else {
            row = 0;
            col = N - (k % N) - 1;
            dir = 1;
        }

        return new int[]{area, row, col, dir};
    }

    private static int[] move(int[] n1) {
        //팀원 리스트 구함
        ArrayList<int[]> list = getTeamPosition(n1);

        //한명씩 이동 -> 첫번째만 갈 곳 정하고 그 다음부턴 이전의 위치로 변경
        //첫번째 이동
        int[] one = n1;//첫번째가 이동한 위치 저장 (1이 3으로 이동했을 때 4로 덮어씌워지는것 방지)
        for (int d = 0; d < 4; d++) {
            int nx = n1[0] + dir[d][0];
            int ny = n1[1] + dir[d][1];

            //범위 내이고 2가 아닐때
            if (!isRange(nx, ny) || map[nx][ny] == 0) continue;
            if (map[nx][ny] != 2) {
                map[nx][ny] = map[n1[0]][n1[1]]; //1번은 0,2가 아닌 곳으로 이동
                one = new int[]{nx, ny};
                break; //더 볼 것 없음
            }
        }

        int[] next = n1; //다음 사람이 이동할 곳
        //남은 위치 이동
        for (int i = 1; i < list.size(); i++) {
            //위치 이동
            int[] cur = list.get(i);
            map[next[0]][next[1]] = map[cur[0]][cur[1]]; //앞의 사람이 옮겨간 자리에 채우기
            if (i == list.size() - 1) {
                map[next[0]][next[1]] = 3; //마지막 값이라면 1이 덮어씌운 값으로 들어가는 것 방지3 처리
            }
            map[cur[0]][cur[1]] = 4; //자신이 있던 곳 빈곳 처리
            next = cur; //다음 채울 곳 갱신
        }
        //1이 3으로 이동했을 때 마지막에 4로 덮어 씌워지는 것 방지
        map[one[0]][one[1]] = 1;

        //1의 위치 갱신
        return one;
    }

    private static ArrayList<int[]> getTeamPosition(int[] n1) {
        Queue<int[]> q = new ArrayDeque<>(); //방문확인
        q.offer(n1);
        boolean[][] v = new boolean[N][N];
        v[n1[0]][n1[1]] = true;
        ArrayList<int[]> list = new ArrayList<>(); //팀들 위치 저장 리스트
        list.add(n1);

        //bfs로 팀원 위치 구함
        while (!q.isEmpty()) {
            int[] cur = q.poll();

            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dir[d][0];
                int ny = cur[1] + dir[d][1];

                if (!isRange(nx, ny) || map[nx][ny] == 0 || map[nx][ny] == 4 || v[nx][ny]) continue;
                //나의 값보다 같거나 하나 클때만 이동
                if ((map[cur[0]][cur[1]] == 1 && map[nx][ny] == 2)
                        || (map[cur[0]][cur[1]] == 2 && map[cur[0]][cur[1]] <= map[nx][ny])) {
                    //1이면 2로만 가고, 2라면 같거나 큰곳으로만
                    v[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                    list.add(new int[]{nx, ny}); //팀원 위치 저장
                }
            }
        }
        return list;
    }

    private static boolean isRange(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N) return false;
        return true;
    }


}