💻 문제
- 삼성 SW 역량테스트 2022 상반기 오전 1번 문제
- 시뮬레이션
🔐 풀이
- 시간: 2시간 20분
아이디어
이 문제의 핵심은 아무래도 술래를 달팽이 모양으로 옮기는 데 있습니다.
시간에 따라서 위치를 바뀌므로 값을 전역변수로 두고 계속 갱신해주는 방법으로 접근했습니다.
규칙적으로 돌아가는데 그게 아닌 예외 경우를 조건 처리해서 값을 할당해주었습니다. 예외 처리해야하는 부분은 방향이 바뀌는 부분으로 조금 수학적으로 접근해보았습니다.
예외의 경우는 (0, 0) (N/2, N/2) 좌표와 제 1사분면에서 y = x + 1을 만족하는 좌표 그리고 제 2, 4사분면에서 x + y = N-1을 만족하는 좌표, 제 3사분면에서 y = x를 만족하는 좌표 이렇게 접근해주었습니다.
이 밖에 코드 리뷰를 통해서 술래의 위치를 관리해주는 방법을 깨달았습니다. 비슷한 맥락으로 어차피 술래가 가는 곳은 정해져있으니 미리 K만큼 (2차원 배열이나 Queue 등에) 저장해두고 시간에 맞춰서 꺼내쓰는 방법입니다. K의 범위가 100 이하이기 때문에 시간에서도 문제가 없을 것이라 생각합니다.
추가로 저는 도망자의 정보를 정적인 배열로 관리해주었기 때문에 도망자의 구조체에 alive 변수를 추가하여 잡혔는지 아닌지에 대한 정보를 관리하였고 이동할 때나 술래잡기할 때 잡혔는지 여부에 대한 정보를 확인하고 처리해주었습니다.
시간복잡도
K번 동안 술래와 도망자가 이동하는데 술래는 O(1)이고 도망자는 M명이므로 O(M)입니다.
O(KM)👉 제출 코드
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int ans;
static int N, M, H, K; // n은 홀수
static boolean[][] trees;
static Node[] people;
static int X, Y, D; // 술래의 위치
static boolean reverse;
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());
trees = new boolean[N][N];
people = new Node[M];
X = N / 2; Y = N / 2;
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 tmp = Integer.parseInt(st.nextToken());
// 도망자 종류 두 가지
// 좌우로 움직이는 사람 오른쪽 보고 시작
// 상하로 움직이는 사람 아래 보고 시작
int d = tmp == 1 ? 1 : 2;
people[i] = new Node(x, y, d, true);
}
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;
trees[x][y] = true;
}
// 나무랑 도망자 중복 위치 가능
for (int i = 0; i < K; i++) {
for (int j = 0; j < M; j++) {
// 술래와 거리가 3 이하이고 살아있는 도망자에 대해서
if (people[j].alive && getDist(X, people[j].x, Y, people[j].y) <= 3) {
moveRunner(j);
}
}
moveIt();
go(i+1);
}
System.out.println(ans);
}
public static void moveRunner(int num) {
// 바라보고 있는 방향으로 1칸 이동
Node p = people[num];
int nx = p.x + dx[p.d];
int ny = p.y + dy[p.d];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
p.d = (p.d + 2) % 4; // 방향 바꾸기
nx = p.x + dx[p.d];
ny = p.y + dy[p.d];
if (X == nx && Y == ny) return;
p.x = nx; p.y = ny; // 술래 없을 때 이동
} else {
if (X == nx && Y == ny) return;
// 술래 없을 때 이동 (나무 있어도)
p.x = nx; p.y = ny;
}
}
public static void moveIt() {
// 시간을 기준으로 위치가 바뀜 -> 값을 할당하자 즉, 움직이고 해당 위치에 대해 방향 갱신하여 관리
X += dx[D];
Y += dy[D];
// 이동 후 방향 틀어지는 지점이면 방향을 바로 틀어줌
if (X == N / 2 && Y == N / 2) {
D = (D + 2) % 4;
if (reverse) reverse = !reverse;
} else if (X == N/2-1 && Y == N /2 ) {
if (reverse) {
D = (D - 1 + 4) % 4;
} else {
D = (D + 1) % 4;
}
} else if (X == 0 && Y == 0) {
D = (D + 2) % 4; // 반대 방향
reverse = true;
} else if (X >= N / 2 || Y >= N / 2) {
if (X == Y || X + Y == N -1) {
// 2, 3, 4사분면에 대해서
if (reverse) {
D = (D - 1 + 4) % 4;
} else {
D = (D + 1) % 4;
}
}
} else if (X < N /2 && Y < N / 2) {
// 1사분면
if (X + 1 == Y) {
if (reverse) {
D = (D - 1 + 4) % 4;
} else {
D = (D + 1) % 4;
}
}
}
// 이외의 경우는 방향 유지
}
public static void go(int turn) {
int runnerCnt = 0; // 잡힌 도망자 개수
// 술래가 바라보고 있는 방향으로 3칸
List<int[]> checkPoint = new ArrayList<>();
for (int i = 0; i < 3; i++) {
int nx = X + dx[D] * i;
int ny = Y + dy[D] * i;
// 범위 밖 확인 + 나무가 있는 칸은 안 보임
if (nx < 0 || nx >= N || ny < 0 || ny >= N || trees[nx][ny]) continue;
checkPoint.add(new int[] {nx, ny});
}
// 술래 개수 세고 잡기
for (int i = 0; i < checkPoint.size(); i++) {
int[] pos = checkPoint.get(i);
for (int num = 0; num < M; num++) {
if (people[num].alive && people[num].x == pos[0] && people[num].y == pos[1]) {
runnerCnt++;
people[num].alive = false;
}
}
}
ans += turn * runnerCnt;
}
public static int getDist(int x1, int x2, int y1, int y2) {
return Math.abs(x1-x2) + Math.abs(y1-y2);
}
static class Node {
int x, y, d;
boolean alive;
Node (int x, int y, int d, boolean alive) {
this.x = x;
this.y = y;
this.d = d;
this.alive = alive;
}
@Override
public String toString() {
return x + " " + y + " " + d;
}
}
}
's Coding Memory