[알고리즘, 코드트리] 루돌프의 반란 - java

문제

문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

요약하자면 아래와 같다. 총 네 가지 동작을 수행해야 한다.

(1) 루돌프의 움직임 : 루돌프는 가장 가까운 산타를 향해 1칸 돌진합니다.

(2) 산타의 움직임 : 산타는 1번부터 P번까지 순서대로 움직입니다. 산타는 루돌프에게 거리가 가장 가까워지는 방향으로 1칸 이동합니다.

(3) 충돌 : 산타와 루돌프가 같은 칸에 있게 되면 충돌이 발생합니다. 루돌프가 움직여서 충돌이 일어난 경우, 해당 산타는 C만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 루돌프가 이동해 온 방향으로 C 칸 만큼 밀려나게 됩니다. 산타가 움직여서 충돌이 일어난 경우, 해당 산타는 D만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 자신이 이동해 온 반대 방향으로 D 칸 만큼 밀려나게 됩니다.

(4) 상호작용 : 루돌프와의 충돌 후 산타는 포물선의 궤적으로 이동하여 착지하게 되는 칸에서만 상호작용이 발생할 수 있습니다. 산타는 충돌 후 착지하게 되는 칸에 다른 산타가 있다면 그 산타는 1칸 해당 방향으로 밀려나게 됩니다.

삼성 기출은 어쩐지 풀면풀수록 괴랄한 유형밖에 없다. 문제의 가장 최선의 방법은 침착하게 지문을 숙달하고 코드의 구조를 짜야한다는 것을 다시 한번 체감한다.

입력

첫 번째 줄에 N, M, P, C, D가 공백을 사이에 두고 주어집니다.

다음 줄에는 루돌프의 초기 위치 (Rr​,Rc​) 가 주어집니다.

다음 P 개의 줄에 걸쳐서 산타의 번호 Pn​과 초기 위치 (Sr​,Sc​)가 공백을 사이에 두고 주어집니다.

처음 산타와 루돌프의 위치는 겹쳐져 주어지지 않음을 가정해도 좋습니다.

• N: 게임판의 크기 (3≤N≤50)
• M: 게임 턴 수 (1≤M≤1000)
• P: 산타의 수 (1≤P≤30)
• C: 루돌프의 힘 (1≤C≤N)
• D: 산타의 힘 (1≤D≤N)
• Pn​: 산타의 번호 (1≤Pn​≤P)
• (Rr​,Rc​): 루돌프의 초기 위치 (1≤Rr​,Rc​≤N)
• (Sr​,Sc​): 산타의 초기 위치 (1≤Sr​,Sc​≤N)

출력

게임이 끝났을 때 각 산타가 얻은 최종 점수를 1번부터 P번까지 순서대로 공백을 사이에 두고 출력합니다.

문제 풀이

어쩐지 익숙한 문제이다. 바다의 짠내와 함께 백준의 친구 상어들이 머릿속을 지나가는.... 그런 유형이다. 이런 유형의 문제가 아직 어려운 사람은 백준 알고리즘에서 상어 시리즈를 정독하고 오자. 연습만이 살 길이다.

백준엔 이보다 악랄한 상어들이 즐비하다.

자료구조 정의 및 입출력

static class Santa {
    int r;
    int c;
    int stunned; // 충돌이 발생했던 턴 + 1
    int score;
    boolean out = false;

    Santa(int r, int c) {
        this.r = r;
        this.c = c;
        stunned = -1;
        score = 0;
    }
}
static Map<Integer, Santa> santaMap = new HashMap<>();
static ArrayList<Integer> santaArr = new ArrayList<>();

static int[][] map;

static int[] dr_santa = {-1, 0, 1, 0};
static int[] dc_santa = {0, 1, 0, -1};
static int[] dr_dear = {-1, -1, 0, 1, 1, 1, 0, -1};
static int[] dc_dear = {0, 1, 1, 1, 0, -1, -1, -1};

산타의 위치(r, c)와 기절해 있을 턴(stunned), 산타가 얻은 점수(score)를 저장할 산타 객체를 선언한다. santa의 번호와 함께 santa를 저장할 santaMap과 santa의 번호를 저장할 santaArr을 선언한다.

 

또한 산타와 루돌프가 이동할 수 있는 방향도 dr과 dc로 선언한다.

N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
P = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());

map = new int[N][N];

st = new StringTokenizer(br.readLine());
Rr = Integer.parseInt(st.nextToken()) - 1;
Rc = Integer.parseInt(st.nextToken()) - 1;
// -1이 루돌프
map[Rr][Rc] = -1; 

for(int i = 0; i < P; i++) {
    st = new StringTokenizer(br.readLine());

    int Pn = Integer.parseInt(st.nextToken());
    int Sr = Integer.parseInt(st.nextToken());
    int Sc = Integer.parseInt(st.nextToken());

    santaMap.put(Pn, new Santa(Sr - 1, Sc - 1));
    santaArr.add(Pn);

    map[Sr - 1][Sc - 1] = Pn;
}
Collections.sort(santaArr);

입출력을 받는다. 선언한 자료구조에 입력받은 정보들을 저장하자.

2차원 map에는 산타의 번호를 저장하고 루돌프는 -1로 표현한다.

 

이 때, 산타가 꼭 번호의 오름차순으로 정렬되어 들어오지 않음에 유의한다. 따라서 Collections.sort()를 사용하여 산타의 번호 배열을 정렬해주었다.

boolean flag = true;
while(flag && m++ < M) {
    move_dear();

    move_santa();

    flag = adjustment();
}

입출력이 끝난 후 위와 같은 구조로 문제를 정의하였다.

사슴이 먼저 움직이자 _ move_dear()

static void move_dear() {
    Santa min_dist_santa = new Santa(-1, -1); // 아무값이나 초기화
    int min_dist = Integer.MAX_VALUE;

	// 가장 가까운 산타 찾기
    for(int Pn : santaArr) {
        Santa santa = santaMap.get(Pn);

        if(santa.out) {
            continue;
        }

        int dist = getDistance(santa.r, Rr, santa.c, Rc);
        if(min_dist > dist) {
            min_dist = dist;
            min_dist_santa = santa;
        } 
        else if(min_dist == dist && cmp(santa, min_dist_santa)) {
            min_dist = dist;
            min_dist_santa = santa;
        }
    }

	// 가장 가까운 산타로 가는 최적 루트 찾기
    min_dist = Integer.MAX_VALUE;
    int min_direction = -1;
    int nextR = 0, nextC = 0;
    for(int d = 0; d < 8; d++) {
        nextR = Rr + dr_dear[d];
        nextC = Rc + dc_dear[d];

        if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
            continue;
        }

        int dist = getDistance(min_dist_santa.r, nextR, min_dist_santa.c, nextC);
        if(min_dist > dist) {
            min_dist = dist;
            min_direction = d;
        }
    }

    // 루돌프 이동
    map[Rr][Rc] = 0;
    nextR = Rr + dr_dear[min_direction];
    nextC = Rc + dc_dear[min_direction];

    // 산타와 충돌 시
    if(map[nextR][nextC] > 0) {
        // 루돌프가 밀고 들어온 방향으로 C 밀려나는 'map[nextR][nextC]'번 산타
        int Pn = map[nextR][nextC];

        // 산타 튕겨나감
        Santa santa = santaMap.get(Pn);
        santa.score += C;

        // 산타 기절
        santa.stunned = m + 1;
        int santaR = nextR + dr_dear[min_direction] * C;
        int santaC = nextC + dc_dear[min_direction] * C;

        interaction(map[nextR][nextC], santaR, santaC, dr_dear[min_direction], dc_dear[min_direction]);
    }

    map[nextR][nextC] = -1;
    Rr = nextR;
    Rc = nextC;
}

루돌프의 움직임은 다음과 같이 정의할 수 있다.

(1) 현재 루돌프의 위치(Rr, Rc)에서 가장 가까운 산타를 찾는다.

(2) 가장 가까운 산타로 가는 최적의 루트를 찾는다.

(3) 루돌프가 이동한다.

(4) 산타와 충돌했다면 산타를 튕겨낸다

(추가) 상호작용 함수를 호출한다.

색깔 표시는 조건부 실행이다.

가장 가까운 산타 찾기

Santa min_dist_santa = new Santa(-1, -1); // 아무값이나 초기화
int min_dist = Integer.MAX_VALUE;

for(int Pn : santaArr) {
    Santa santa = santaMap.get(Pn);

    if(santa.out) {
        continue;
    }

    int dist = getDistance(santa.r, Rr, santa.c, Rc);
    if(min_dist > dist) {
        min_dist = dist;
        min_dist_santa = santa;
    } 
    else if(min_dist == dist && cmp(santa, min_dist_santa)) {
        min_dist = dist;
        min_dist_santa = santa;
    }
}

현재까지 아웃되지 않은 산타에 대하여 가장 가까운 산타를 찾는다. 이때 거리 계산을 위한 함수 getDistance를 따로 선언하여 계속 재활용할 것이다.

static int getDistance(int r1, int r2, int c1, int c2) {
    return (int)Math.pow(r1 - r2, 2) + (int)Math.pow(c1 - c2, 2);
}

최적의 루트 찾기

min_dist = Integer.MAX_VALUE;
int min_direction = -1;
int nextR = 0, nextC = 0;
for(int d = 0; d < 8; d++) {
    nextR = Rr + dr_dear[d];
    nextC = Rc + dc_dear[d];

    if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
        continue;
    }

    int dist = getDistance(min_dist_santa.r, nextR, min_dist_santa.c, nextC);
    if(min_dist > dist) {
        min_dist = dist;
        min_direction = d;
    }
}

비슷한 로직으로 가장 가까운 산타로 가는 최적의 방향을 선택한다.

루돌프가 이동한다. 이때?!?!?

// 루돌프 이동
map[Rr][Rc] = 0;
nextR = Rr + dr_dear[min_direction];
nextC = Rc + dc_dear[min_direction];

// 산타와 충돌 시
if(map[nextR][nextC] > 0) {
    // 루돌프가 밀고 들어온 방향으로 C 밀려나는 'map[nextR][nextC]'번 산타
    int Pn = map[nextR][nextC];

    // 산타 튕겨나감
    Santa santa = santaMap.get(Pn);
    santa.score += C;

    // 산타 기절
    santa.stunned = m + 1;
    int santaR = nextR + dr_dear[min_direction] * C;
    int santaC = nextC + dc_dear[min_direction] * C;

    interaction(map[nextR][nextC], santaR, santaC, dr_dear[min_direction], dc_dear[min_direction]);
}

map[nextR][nextC] = -1;
Rr = nextR;
Rc = nextC;

루돌프가 해당 방향으로 이동했을 때, 그 칸에 이미 산타가 존재한다면(map[nextR][nextC] > 0) 산타와 루돌프가 충돌한 상황이라고 간주한다. 따라서 부딪힌 산타의 점수를 올려주고 산타의 기절을 {현재 턴} + 1 로 초기화한다.

 

그후 산타의 번호, 산타의 R 좌표, 산타의 C 좌표, 산타가 밀려날 방향 dr, 산타가 밀려날 방향 dc를 상호작용 함수로 넘겨준다. 상호작용 함수에 대해서는 후술하겠다.

산타의 이동 _ move_santa()

static void move_santa() {
    for(int Pn : santaArr) {
        Santa santa = santaMap.get(Pn);

        if(santa.out) {
            continue;
        }

        if(santa.stunned >= m) {
            continue;
        }

        int min_dist = getDistance(santa.r, Rr ,santa.c, Rc);
        int min_direction = -1;
        int nextR = 0, nextC = 0;
        for(int d = 0; d < 4; d++) {
            nextR = santa.r + dr_santa[d];
            nextC = santa.c + dc_santa[d];

            if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
                continue;
            }
            // 이미 다른 산타가 있으면
            if(map[nextR][nextC] > 0) {
                continue;
            }

            int dist = getDistance(nextR, Rr, nextC, Rc);
            if(min_dist > dist) {
                min_dist = dist;
                min_direction = d;
            }
        }

        if(min_direction == -1) {
            continue;
        }

        // 산타 이동
        map[santa.r][santa.c] = 0;
        nextR = santa.r + dr_santa[min_direction];
        nextC = santa.c + dc_santa[min_direction];

        // 루돌프와 충돌하면
        if(map[nextR][nextC] == -1) {
            santa.score += D;

            // min_direction 반대 방향으로 D만큼 튕겨나감
            int opposite_direction = (min_direction + 2) % 4;
            nextR += dr_santa[opposite_direction] * D;
            nextC += dc_santa[opposite_direction] * D;

            // 다음 라운드까지 santa 기절
            santa.stunned = m + 1;

            // nextR, nextC, direction에서 산타끼리 상호작용
            interaction(Pn, nextR, nextC, dr_santa[opposite_direction], dc_santa[opposite_direction]);

            // 맵 밖으로 벗어났다면 
            if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
                continue;
            }
        }

        santa.r = nextR;
        santa.c = nextC;
        map[nextR][nextC] = Pn;
    }
}

흐름은 루돌프의 이동 함수와 유사하다. 산타의 동작은 아래와 같이 구조화할 수 있다.

(1) 산타가 아웃되었거나 현재 턴에 기절 중이라면 움직이지 못한다.

(2) 산타가 루돌프로 가장 가까워지는 칸을 찾는다.

(3) 산타가 최적 루트 칸으로 움직인다.

(4) 해당 칸에 루돌프가 존재한다면? 산타가 튕겨나간다.

(추가) 상호작용 함수를 호출한다.

마찬가지로 노란색은 조건부로 실행한다.

산타가 루돌프로 가는 최적 루트

int min_dist = getDistance(santa.r, Rr ,santa.c, Rc);
int min_direction = -1;
int nextR = 0, nextC = 0;
for(int d = 0; d < 4; d++) {
    nextR = santa.r + dr_santa[d];
    nextC = santa.c + dc_santa[d];

    if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
        continue;
    }
    // 이미 다른 산타가 있으면
    if(map[nextR][nextC] > 0) {
        continue;
    }

    int dist = getDistance(nextR, Rr, nextC, Rc);
    if(min_dist > dist) {
        min_dist = dist;
        min_direction = d;
    }
}

if(min_direction == -1) {
    continue;
}

산타의 현재 위치(santa.r, santa.c)로 min_dist를 초기화해야 함에 유의하자. 너무 큰 값을 초기화 해버리면 최적의 루트를 선택하지 못하는 경우에 움직이지 않는다는 조건을 만족할 수 없다.

산타가 이동한다. 이때?!?!?!?

// 산타 이동
map[santa.r][santa.c] = 0;
nextR = santa.r + dr_santa[min_direction];
nextC = santa.c + dc_santa[min_direction];

// 루돌프와 충돌하면
if(map[nextR][nextC] == -1) {
    santa.score += D;

    // min_direction 반대 방향으로 D만큼 튕겨나감
    int opposite_direction = (min_direction + 2) % 4;
    nextR += dr_santa[opposite_direction] * D;
    nextC += dc_santa[opposite_direction] * D;

    // 다음 라운드까지 santa 기절
    santa.stunned = m + 1;

    // nextR, nextC, direction에서 산타끼리 상호작용
    interaction(Pn, nextR, nextC, dr_santa[opposite_direction], dc_santa[opposite_direction]);

    // 맵 밖으로 벗어났다면 
    if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
        continue;
    }
}

santa.r = nextR;
santa.c = nextC;
map[nextR][nextC] = Pn;

이 때도 마찬가지로 루돌프와 충돌하는 경우를 고려해야 한다. 뒤로 밀려난 상황을 표현하기 위해 상호작용 함수를 호출하자.

상호작용 함수 _ interation()

static private void interaction(int Pn, int nextR, int nextC, int dr, int dc) {
    // 맵 밖일 때
    if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
        Santa santa = santaMap.get(Pn);
        santa.out = true;

        return;
    }
    // 빈칸 일때
    if(map[nextR][nextC] == 0) {
        map[nextR][nextC] = Pn;
        Santa santa = santaMap.get(Pn);
        santa.r = nextR;
        santa.c = nextC;

        return;
    }

    int nextPn = map[nextR][nextC];

    interaction(nextPn, nextR + dr, nextC + dc, dr, dc);

    map[nextR][nextC] = Pn;
    Santa santa = santaMap.get(Pn);
    santa.r = nextR;
    santa.c = nextC;
}

산타가 뒤로 밀려났을 때, 해당 칸에도 산타가 존재하는 상황을 고민하기 위해서 백트래킹을 사용했다. 재귀 호출의 마지막 산타가 빈칸으로 가거나 맵 밖으로 나간 경우 재귀 호출을 돌아오면서 산타의 위치를 map에 반영한다.

 

코드로 본다면 이해하기 어렵지 않을 것이다.

정산 함수 _ adjustment()

static private boolean adjustment() {
    boolean flag = false;

    for(int Pn : santaArr) {
        Santa santa = santaMap.get(Pn);

        if(!santa.out) {
            santa.score++;
            flag = true;
        }
    }
    return flag;
}

현재 라운드에 아웃되어있지 않은 산타들은 score를 1씩 올려준다.

전체 코드

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

public class Main {
    static int N, M, P, C, D;
    static int m = 0;
    static int Rr, Rc;
    
    static class Santa {
        int r;
        int c;
        int stunned; // 기절한 턴
        int score;
        boolean out = false;

        Santa(int r, int c) {
            this.r = r;
            this.c = c;
            stunned = -1;
            score = 0;
        }
    }
    static Map<Integer, Santa> santaMap = new HashMap<>();
    static ArrayList<Integer> santaArr = new ArrayList<>();

    static int[][] map;

    static int[] dr_santa = {-1, 0, 1, 0};
    static int[] dc_santa = {0, 1, 0, -1};
    static int[] dr_dear = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dc_dear = {0, 1, 1, 1, 0, -1, -1, -1};

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

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        map = new int[N][N];

        st = new StringTokenizer(br.readLine());
        Rr = Integer.parseInt(st.nextToken()) - 1;
        Rc = Integer.parseInt(st.nextToken()) - 1;
        // -1이 루돌프
        map[Rr][Rc] = -1; 

        for(int i = 0; i < P; i++) {
            st = new StringTokenizer(br.readLine());

            int Pn = Integer.parseInt(st.nextToken());
            int Sr = Integer.parseInt(st.nextToken());
            int Sc = Integer.parseInt(st.nextToken());

            santaMap.put(Pn, new Santa(Sr - 1, Sc - 1));
            santaArr.add(Pn);
            
            map[Sr - 1][Sc - 1] = Pn;
        }
        Collections.sort(santaArr);

        boolean flag = true;
        while(flag && m++ < M) {
            move_dear();

            move_santa();

            flag = adjustment();
        }

        StringBuilder sb = new StringBuilder();
        for(int Pn : santaArr) {
            Santa santa = santaMap.get(Pn);

            sb.append(santa.score).append(" ");
        }

        System.out.println(sb);
    }

    static void move_dear() {
        Santa min_dist_santa = new Santa(-1, -1); // 아무값이나 초기화
        int min_dist = Integer.MAX_VALUE;

        for(int Pn : santaArr) {
            Santa santa = santaMap.get(Pn);

            if(santa.out) {
                continue;
            }

            int dist = getDistance(santa.r, Rr, santa.c, Rc);
            if(min_dist > dist) {
                min_dist = dist;
                min_dist_santa = santa;
            } 
            else if(min_dist == dist && cmp(santa, min_dist_santa)) {
                min_dist = dist;
                min_dist_santa = santa;
            }
        }
        
        min_dist = Integer.MAX_VALUE;
        int min_direction = -1;
        int nextR = 0, nextC = 0;
        for(int d = 0; d < 8; d++) {
            nextR = Rr + dr_dear[d];
            nextC = Rc + dc_dear[d];

            if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
                continue;
            }

            int dist = getDistance(min_dist_santa.r, nextR, min_dist_santa.c, nextC);
            if(min_dist > dist) {
                min_dist = dist;
                min_direction = d;
            }
        }

        // 루돌프 이동
        map[Rr][Rc] = 0;
        nextR = Rr + dr_dear[min_direction];
        nextC = Rc + dc_dear[min_direction];

        // 산타와 충돌 시
        if(map[nextR][nextC] > 0) {
            // 루돌프가 밀고 들어온 방향으로 C 밀려나는 'map[nextR][nextC]'번 산타
            int Pn = map[nextR][nextC];

            // 산타 튕겨나감
            Santa santa = santaMap.get(Pn);
            santa.score += C;

            // 산타 기절
            santa.stunned = m + 1;
            int santaR = nextR + dr_dear[min_direction] * C;
            int santaC = nextC + dc_dear[min_direction] * C;

            interaction(map[nextR][nextC], santaR, santaC, dr_dear[min_direction], dc_dear[min_direction]);
        }

        map[nextR][nextC] = -1;
        Rr = nextR;
        Rc = nextC;
    }

    static boolean cmp(Santa q1, Santa q2) {
        if(q1.r == q2.r) {
            return q1.c > q2.c;
        }
        return q1.r > q2.r;
    }

    static int getDistance(int r1, int r2, int c1, int c2) {
        return (int)Math.pow(r1 - r2, 2) + (int)Math.pow(c1 - c2, 2);
    }

    static void move_santa() {
        for(int Pn : santaArr) {
            Santa santa = santaMap.get(Pn);

            if(santa.out) {
                continue;
            }

            if(santa.stunned >= m) {
                continue;
            }

            int min_dist = getDistance(santa.r, Rr ,santa.c, Rc);
            int min_direction = -1;
            int nextR = 0, nextC = 0;
            for(int d = 0; d < 4; d++) {
                nextR = santa.r + dr_santa[d];
                nextC = santa.c + dc_santa[d];

                if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
                    continue;
                }
                // 이미 다른 산타가 있으면
                if(map[nextR][nextC] > 0) {
                    continue;
                }

                int dist = getDistance(nextR, Rr, nextC, Rc);
                if(min_dist > dist) {
                    min_dist = dist;
                    min_direction = d;
                }
            }

            if(min_direction == -1) {
                continue;
            }

            // 산타 이동
            map[santa.r][santa.c] = 0;
            nextR = santa.r + dr_santa[min_direction];
            nextC = santa.c + dc_santa[min_direction];

            // 루돌프와 충돌하면
            if(map[nextR][nextC] == -1) {
                santa.score += D;

                // min_direction 반대 방향으로 D만큼 튕겨나감
                int opposite_direction = (min_direction + 2) % 4;
                nextR += dr_santa[opposite_direction] * D;
                nextC += dc_santa[opposite_direction] * D;
                
                // 다음 라운드까지 santa 기절
                santa.stunned = m + 1;
                
                // nextR, nextC, direction에서 산타끼리 상호작용
                interaction(Pn, nextR, nextC, dr_santa[opposite_direction], dc_santa[opposite_direction]);
                
                // 맵 밖으로 벗어났다면 
                if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
                    continue;
                }
            }

            santa.r = nextR;
            santa.c = nextC;
            map[nextR][nextC] = Pn;
        }
    }

    static private void interaction(int Pn, int nextR, int nextC, int dr, int dc) {
        // 맵 밖일 때
        if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) {
            Santa santa = santaMap.get(Pn);
            santa.out = true;

            return;
        }
        // 빈칸 일때
        if(map[nextR][nextC] == 0) {
            map[nextR][nextC] = Pn;
            Santa santa = santaMap.get(Pn);
            santa.r = nextR;
            santa.c = nextC;
            
            return;
        }

        int nextPn = map[nextR][nextC];

        interaction(nextPn, nextR + dr, nextC + dc, dr, dc);

        map[nextR][nextC] = Pn;
        Santa santa = santaMap.get(Pn);
        santa.r = nextR;
        santa.c = nextC;
    }

    static private boolean adjustment() {
        boolean flag = false;

        for(int Pn : santaArr) {
            Santa santa = santaMap.get(Pn);

            if(!santa.out) {
                santa.score++;
                flag = true;
            }
        }
        return flag;
    }
}

문제 풀이 소요 시간 : 2시간 30분

까다로운 구현 문제였다. 흐름을 따라간다면 좀 수월하니 포기하지 말고 도전해보자.