코딩테스트/코드트리
[Java] 코드트리 삼성 SW 역량테스트 기출 문제 : 술래잡기
이덩우
2024. 1. 17. 21:19
핵심포인트
- 도망자 이동
- 동시에 움직이는 상황을 처리하기 위해서는 여러 가지의 방법을 사용할 수 있다.
- 이 문제를 해결할 때는 임시 저장공간을 만든 후, 원본 배열에서 임시 저장공간으로 움직인 후 다시 원본 배열로 복사하는 방식을 사용했다.
- 술래 이동
- 안에서 밖으로 이동
- 방향을 꺾을 때 까지 움직이는 칸 수를 나열해보면 1, 1, 2, 2, 3, 3, 4, 4, .... 이다.
- 따라서 방향을 꺾은 횟수와 현재 진행 방향에서 이동할 수 있는 남은 칸 수를 비교해가며 소용돌이 모양으로 움직여준다.
- 이 때 중요한 점은 *현재 바라보는 방향에서 끝까지 이동했다면 그 즉시 방향을 꺾는 것이다.*
- 마찬가지로 (0, 0) 에 도착했다면 방향을 즉시 꺾어줘야한다.
- 밖에서 안으로 이동
- 오히려 간단했다.
- 현재 밟은 칸에 대해서 방문 처리를 하며 쭉 나아간다.
- 다음 나아갈 칸이 배열의 범위를 벗어나거나, 방문한 곳이라면 방향을 꺾어주는 방식으로 진행하면 된다.
- 나아가다보면 다시 정중앙으로 위치하게 된다.
- 마찬가지로 방향을 바꿔야하는 상황이라면 그 즉시 꺾어준다.
- 안에서 밖으로 이동
솔루션
public class Main {
static int N, M, H, K, score;
static int[] dy = {-1, 0, 1, 0}; // 상 우 하 좌
static int[] dx = {0, 1, 0, -1};
static Boss boss;
static int[][] treeMap;
static ArrayList<Integer>[][] runnerMap;
static int cnt, line;
static boolean inToOut;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
visited = new boolean[N][N];
boss = new Boss(N / 2, N / 2, 0);
treeMap = new int[N][N];
runnerMap = new ArrayList[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
runnerMap[i][j] = new ArrayList<>();
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken()) - 1;
int x = Integer.parseInt(st.nextToken()) - 1;
int dir = Integer.parseInt(st.nextToken());
runnerMap[y][x].add(dir);
}
for (int i = 0; i < H; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken()) - 1;
int x = Integer.parseInt(st.nextToken()) - 1;
treeMap[y][x] = 1;
}
inToOut = true;
cnt = 1;
line = 1;
for (int i = 1; i <= K; i++) {
step1_moveRunner();
step2_moveBoss();
step3_catchRunner(i);
}
System.out.println(score);
}
static void step1_moveRunner() {
ArrayList<Integer>[][] tmp = new ArrayList[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
tmp[i][j] = new ArrayList<>();
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (runnerMap[i][j].size() > 0 && checkDistance(new Pair(i, j))) {
for (Integer curDir : runnerMap[i][j]) {
int nextY = i + dy[curDir];
int nextX = j + dx[curDir];
if (nextY < 0 || nextX < 0 || nextY >= N || nextX >= N) {
curDir = (curDir + 2) % 4;
nextY = i + dy[curDir];
nextX = j + dx[curDir];
}
if (nextY == boss.y && nextX == boss.x) {
tmp[i][j].add(curDir);
} else {
tmp[nextY][nextX].add(curDir);
}
}
} else {
for (Integer curDir : runnerMap[i][j]) {
tmp[i][j].add(curDir);
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
runnerMap[i][j].clear();
for (Integer dir : tmp[i][j]) {
runnerMap[i][j].add(dir);
}
}
}
}
static boolean checkDistance(Pair pair) {
int dy = Math.abs(pair.y - boss.y);
int dx = Math.abs(pair.x - boss.x);
if (dy + dx > 3) {
return false;
} else {
return true;
}
}
static void step2_moveBoss() {
if (inToOut) {
step2_1_inToOut();
} else {
step2_2_outToIn();
}
}
static void step2_1_inToOut() {
int nextY = boss.y + dy[boss.dir];
int nextX = boss.x + dx[boss.dir];
boss.y = nextY;
boss.x = nextX;
cnt--;
if (boss.y == 0 && boss.x == 0) {
visited = new boolean[N][N];
visited[0][0] = true;
inToOut = false;
boss.dir = (boss.dir + 2) % 4;
return;
}
if (cnt == 0) {
line++;
boss.dir = (boss.dir + 1) % 4;
cnt = (line / 2) + (line % 2);
}
}
static void step2_2_outToIn() {
int nextY = boss.y + dy[boss.dir];
int nextX = boss.x + dx[boss.dir];
boss.y = nextY;
boss.x = nextX;
visited[boss.y][boss.x] = true;
if (boss.y == N / 2 && boss.x == N / 2) {
inToOut = true;
cnt = 1;
line = 1;
boss.dir = (boss.dir + 2) % 4;
return;
}
nextY += dy[boss.dir];
nextX += dx[boss.dir];
if (nextY < 0 || nextX < 0 || nextY >= N || nextX >= N || visited[nextY][nextX]) {
boss.dir = (boss.dir + 3) % 4;
}
}
static void step3_catchRunner(int t) {
for (int i = 0; i < 3; i++) {
int targetY = boss.y + i * dy[boss.dir];
int targetX = boss.x + i * dx[boss.dir];
if (targetY < 0 || targetX < 0 || targetY >= N || targetX >= N) return;
if (treeMap[targetY][targetX] == 0 && runnerMap[targetY][targetX].size() > 0) {
score += t * runnerMap[targetY][targetX].size();
runnerMap[targetY][targetX].clear();
}
}
}
static class Boss {
int y;
int x;
int dir;
public Boss(int y, int x, int dir) {
this.y = y;
this.x = x;
this.dir = dir;
}
}
static class Pair {
int y;
int x;
public Pair(int y, int x) {
this.y = y;
this.x = x;
}
}
}