PS/BOJ
5648 원자소멸 시뮬레이션
easy16
2022. 5. 20. 23:13
#전략 1
기존 풀이는 visited 및 check 그리고 dis배열을 활용하여 직관적으로 풀이하려했다.
결과는 13번째 TC에서 fail인데 이유를 구체적으로 알 수가 없고, 시간관계상 다른 풀이를 검색해보았다.
로직상으로 문제가 없다고 생각 되지만, 사용하는 배열이 많아 어딘가 예외적인 케이스가 분명 발생할 것으로 추측된다.
(한마디로 비효율적인 접근법이었다는 의미)
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;
import java.io.PrintStream;
class Solution {
static int N, ans;
static boolean DBG = false;
static class Atom {
int x, y, d, k, id;
int impactTime;// 동시간에 충돌했는지를 확인하기 위한 변수
Atom(int id, int x, int y, int d, int k) {
this.id = id;
this.x = x;
this.y = y;
this.d = d;
this.k = k;
this.impactTime = 0;
}
public void progress() {
x += dx[d];
y += dy[d];
}
public int getDistance(Atom o) {
return Math.abs(x - o.x) + Math.abs(y - o.y);
}
public boolean isImpactable(Atom o) {
int dis = getDistance(o);
// 거리가 0인 경우 충돌 가능
if (dis == 0)
return true;
// 거리가 1이 아닌 경우 충돌 불가
if (dis != 1)
return false;
// x축에 나란한 경우
if (y == o.y) {
if (x < o.x) {
if (d == LEFT && o.d == RIGHT)
return true;
if (d == RIGHT && o.d == LEFT)
return false;
}
if (x > o.x) {
if (d == RIGHT && o.d == LEFT)
return true;
if (d == LEFT && o.d == RIGHT)
return false;
}
}
// y축에 나란한 경우
if (x == o.x) {
if (y < o.y) {
if (d == UP && o.d == DOWN)
return true;
if (d == DOWN && o.d == UP)
return false;
}
if (y > o.y) {
if (d == DOWN && o.d == UP)
return true;
if (d == UP && o.d == DOWN)
return false;
}
}
if (DBG)
System.out.printf("unexpected false id [%d][%d]return dis : %d x,y[%d %d] o.x,o.y[%d %d]\n", id, o.id,
dis, x, y, o.x, o.y);
return false;
}
}
static int[] dx = { 0, 0, -1, 1 };
static int[] dy = { 1, -1, 0, 0 };
static final int UP = 0;
static final int DOWN = 1;
static final int LEFT = 2;
static final int RIGHT = 3;
static boolean[][] visited;
static boolean[] check;
// static boolean[] visited;
static int[][] dis; // 거리가 멀어지고 있는지 확인하기 위한 dis배열
static Atom[] arr;
static Queue<Atom> queue;
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
if (DBG) {
File file = new File(
"C:\\Users\\Lee\\eclipse-workspace\\TestApplication\\src\\com\\test\\testapplication\\output.txt");
PrintStream ps = new PrintStream(file);
System.setOut(ps);
}
int T;
T = Integer.parseInt(br.readLine());
for (int test_case = 1; test_case <= T; test_case++) {
N = Integer.parseInt(br.readLine());
arr = new Atom[N];
visited = new boolean[N][N];
for ( int i = 0 ; i < N ; i++) {
for ( int j = 0 ; j < N ; j++) {
if (i==j)
visited[i][j]=true;
}
}
check= new boolean[N];
// visited = new boolean[N];
dis = new int[N][N];
queue = new LinkedList<>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int id = i;
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
queue.add(new Atom(id, x, y, d, k));
Arrays.fill(dis[i], Integer.MAX_VALUE);
}
ans = 0;
simultation();
System.out.println("#" + test_case + " " + ans);
}
}
private static void simultation() {
int time = 1;
Atom now;
while (!queue.isEmpty()) {
int size = queue.size();
// 점 하나는 해결할 수 없다.
if (size == 1)
return;
if (DBG)
System.out.println("@@@@@@@time : " + time + " qsize : " + size);
for (int q = 0; q < size; ++q) {
now = queue.poll();
int nowId = now.id;
// 충돌여부 확인
for (Atom atom : queue) {
// 비교대상의 id
int nextId = atom.id;
// 이미 충돌했고, 충돌시간이 현재 시각과 다르면 건너 뜀.
if (visited[nowId][nextId] && atom.impactTime != 0)
continue;
int currentDis = now.getDistance(atom);
if (DBG)
System.out.printf("DBG[%d][%d][dis : %d][%d and %d] ans : %d\n", nowId, nextId,
dis[nowId][nextId], nowId, nextId, ans);
// 현재거리가 이전 거리보다 멀어졌으면, 영원히 만나지 않으므로 방문처리.
if (dis[nowId][nextId] <= currentDis) {
if (DBG)
System.out.printf(
"CRITICAL : nowId :%d and nextId %d never meet dis : %d currentDis : %d\n", nowId,
nextId, dis[nowId][nextId], currentDis);
visited[nowId][nextId] = true;
visited[nextId][nowId] = true;
continue;
}
dis[nowId][nextId] = currentDis;
if (now.isImpactable(atom)) {
// 상대를 방문처리. -> 디버깅 후 위의 로직과 합해도 됨.
visited[nowId][nextId] = true;
visited[nextId][nowId] = true;
atom.impactTime = time;
now.impactTime = time;
if(!check[nextId] ) {
ans += atom.k;
check[nextId]=true;
}
if (!check[nowId]) {
ans += now.k;
check[nowId]=true;
}
if (DBG)
System.out.printf("[dis : %d][%d and %d] crashed ans : %d\n", dis[nowId][nextId], nowId,
nextId, ans);
}
}
boolean isAllVisited = true;
for ( int i = 0 ; i < N ; i++) {
for ( int j = 0 ; j < N; j++) {
if( i!=j && !visited[i][j]) {
isAllVisited = false;
break;
}
}
}
/*
for (boolean[] ar : visited) {
for (boolean b : ar) {
System.out.printf("%b ",b);
}
System.out.println();
}
*/
if (isAllVisited) {
if (DBG)
System.out.println("ALL atoms visited or never met finish program");
return;
}
// 충돌하지 않은 경우 다시 enqueue
if (!check[now.id])
queue.offer(now);
}
// 모든 검사가 끝난 이후 원자들을 업데이트 해준다.
for (Atom atom : queue) {
// 충돌 시간이 0이 아닌 경우 충돌한것으로 간주
if (atom.impactTime != 0)
continue;
if (DBG)
System.out.printf("move id:%d [x:%5d y:%5d][d : %d]\n", atom.id, atom.x, atom.y, atom.d);
atom.progress();
}
time++;
}
}
}
#전략 2.(남의 답)
역시나 남의 코드를 분석하면 배울점이 많다.
1. 입력
- 최초 입력값을 x, y가 아닌 y, x 로 받아 배열의 x,y를 실제 수학의 좌표와 같이 사용할 수 있도록 구성한다.
*(배열의 최대크기 - x 를 하므로써 배열의 인덱스 반대방향으로 진행하게끔 만듦)
*(x,y 입력 순서가 달라지므로, 기존 배열탐색으로 y/x축 대칭이 일어남)
ex) 2, 3
y= (y + 1000) << 1
=> 2004
x= 4000 - ((x + 1000) <<1)
=> 4000 - 2006
배열인덱스의 (2000,2000)를 원점으로 x는 일반 좌표계의 y축, y는 x축을 의미.
map[1994][2004]는 일반좌표계의 원점(0,0)을 기준으로 (4,6)과 동일하다
위와 같이 shifting으로 2배증가 시킨 이유를 생각해보면 너무 멋지다.
전략1에서 생각했던 대로면, dis값이 0, 1인 경우와 방향을 모두 고려해야 충돌여부를 판단할 수 있으나,
scale이 2배가 되면, 아래 코드와 같이 map의 값을 순차적으로 이동시켜도 중복이 발생하지 않게 된다.
ex)
아래의 예에서 현재 값을 이동하고 다음 값을 이동하게 되면, 어쩔 수 없이 기존값에 영향을 받게 된다.
(o)=><=(o)
하지만 scale이 2배가 되면?
(o)=>( )<=(o)
좌,우 어떤 값이든 먼저 옮긴 후, 나머지를 차례로 옮겨도 결과에는 차이가 없게된다.
이게 상,하,좌,우 모두에 통하기 때문에 아래와 같이 코드가 간결해진다.
경계에 도달하는 경우는 겹치는 원자가 없음을 나타내며 map의 값이 현재(now) 값과 다른 것은 충돌이 일어났음을 의미한다.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;
import java.io.PrintStream;
class Solution {
static int N, ans;
static boolean DBG = false;
static class Atom {
int x, y, d, k;
Atom( int x, int y, int d, int k) {
this.x = x;
this.y = y;
this.d = d;
this.k = k;
}
}
static int[] dx = { -1, 1, 0, 0 };//xy대칭 및 부호가 반대
static int[] dy = { 0, 0 , -1,1 };//xy대칭
static final int UP = 0;
static final int DOWN = 1;
static final int LEFT = 2;
static final int RIGHT = 3;
static int[][] map;
static Queue<Atom> queue;
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T;
T = Integer.parseInt(br.readLine());
for (int test_case = 1; test_case <= T; test_case++) {
N = Integer.parseInt(br.readLine());
queue = new LinkedList<>();
map = new int[4002][4002];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
//x의 부호를 변경하고 x,y를 대칭으로 만들어 실제 좌표계와 같이 사용할 수 있게 변형됨.
int y = Integer.parseInt(st.nextToken());
y = ((y+1000)<<1);
int x = Integer.parseInt(st.nextToken());
x = 4000 - ( (x+ 1000) <<1));
int d = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
map[x][y] = k;
queue.add(new Atom(x,y,d,k));
}
ans = 0;
bfs();
System.out.println("#" + test_case + " " + ans);
}
}
private static void bfs() {
while(!queue.isEmpty()) {
Atom n = queue.poll();
//현재 자리가 내가 가진 값과 다른때
if ( map[n.x][n.y] != n.k) {
ans += map[n.x][n.y];
map[n.x][n.y] =0;
continue;
}
int nx = n.x + dx[n.d];
int ny = n.y + dy[n.d];
if( nx>=0 && nx <=4000 && ny >=0 && ny <= 4000) {
if(map[nx][ny] == 0) {
map[nx][ny] = n.k;
queue.add(new Atom(nx,ny,n.d,n.k));
}
else {
map[nx][ny] += n.k;
}
}
//원래 있던 곳을 비움
map[n.x][n.y] = 0;
}
}
}