첫번째 시도 -> 실패

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class swea_5648_원자소멸시뮬레이션 {
 
    static int totalCase = 0;
    static int atoms = 0;
    static class atomsInfo {
        int x;
        int y;
        int dir;
        int energy;
        atomsInfo(int x, int y, int dir, int energy){
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.energy = energy;
        }
    }
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        totalCase = Integer.parseInt(br.readLine());
        atoms = Integer.parseInt(br.readLine());
        
        // x 위치, y 위치, 이동 방향, 보유 에너지 K
        atomsInfo[] atom = new atomsInfo[atoms];
        
        //init
        
        int[][] board = new int[4001][4001];
        for(int i=0; i<atoms; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int atomX = (Integer.parseInt(st.nextToken()) + 1000) * 2;
            int atomY = (Integer.parseInt(st.nextToken()) + 1000) * 2;
            int atomDir = Integer.parseInt(st.nextToken());
            int atomEnergy = Integer.parseInt(st.nextToken());
            atom[i] = new atomsInfo(atomX, atomY, atomDir, atomEnergy);
            board[atom[i].x][atom[i].y] = 1;
        }
        
        int[][] checkBoard = new int[4001][4001];
        
        int ans = 0;
        whileBreak : while(true) {
            //board 에 원자가 없는지 확인
            boolean goAns = false;
            
            isAtom : for(int i=0; i<4000; i++) {
                for(int j=0; j<4000; j++) {
                    
                    if(board[i][j] == 1) {
                        goAns = true;
                        break isAtom;
                    }
                }
                
            } if(goAns == false) { break whileBreak; } //맵에서 원자가 없을 때까지 조회 
            
            
            //원자 하나하나 를 다 한칸씩 이동
            //상(0), 하(1), 좌(2), 우(3)
            for(int i=0; i<atoms; i++) {
                if(atom[i] == null) continue;
                if(atom[i].dir == 0) {
                    //x 1 증가 
                    board[atom[i].x][atom[i].y]=  0; 
                    if(atom[i].x+1 > 4000) continue ; 
                    atom[i].x  += 1;
                    
                    if(checkBoard[atom[i].x][atom[i].y]!=0) {
                        checkBoard[atom[i].x][atom[i].y]+=atom[i].energy; 
                        atom[i] = null; //이 원자는 더이상 없는거죠! 
                        continue;
                    }else {
                        checkBoard[atom[i].x][atom[i].y]=atom[i].energy;
                    }//부딪혔는지 확인
                    
                    board[atom[i].x][atom[i].y] = 1;
                }else if(atom[i].dir == 1) {
                    //x 1 감소 
                    board[atom[i].x][atom[i].y]=  0; 
                    if(atom[i].x-1 < 0) continue ; 
                    atom[i].x  -= 1;
                    
                    
                    if(checkBoard[atom[i].x][atom[i].y]!=0) {
                        checkBoard[atom[i].x][atom[i].y]+=atom[i].energy;
                        atom[i] = null;
                        continue;
                    }else {
                        checkBoard[atom[i].x][atom[i].y]=atom[i].energy;
                    }//부딪혔는지 확인
                    
                    board[atom[i].x][atom[i].y] = 1;
                }else if(atom[i].dir == 2) {
                    //y 1 감소
                    board[atom[i].x][atom[i].y]=  0; 
                    if(atom[i].y-1 < 0) continue ; 
                    atom[i].y  -= 1;
                    
                    
                    
                    if(checkBoard[atom[i].x][atom[i].y]!=0) {
                        checkBoard[atom[i].x][atom[i].y]+=atom[i].energy;
                        atom[i] = null;
                        continue;
                    }else {
                        checkBoard[atom[i].x][atom[i].y]=atom[i].energy;
                    }//부딪혔는지 확인
                    
                    board[atom[i].x][atom[i].y] = 1;
                }else if(atom[i].dir == 3) {
                    //y 1 증가 
                    board[atom[i].x][atom[i].y]=  0; 
                    if(atom[i].y+1 > 4000) continue ; 
                    atom[i].y  += 1;
                    
                    
                    if(checkBoard[atom[i].x][atom[i].y]!=0) {
                        checkBoard[atom[i].x][atom[i].y]+=atom[i].energy;
                        atom[i] = null;
                        continue;
                    }else {
                        checkBoard[atom[i].x][atom[i].y]=atom[i].energy;
                    }//부딪혔는지 확인
                    
                    board[atom[i].x][atom[i].y] = 1;
                }
            }
            
            
            for(int i=0; i<4000; i++) {
                for(int j=0; j<4000; j++) {
                    if(checkBoard[i][j] != 0) {
                        ans += checkBoard[i][j]; //충돌 한 개수 
                    }
                }
            }//end of for loop
            
            checkBoard = new int[4001][4001];
            
            
            
        }
        //정답 갱신
        System.out.println(ans);
    }
    
 
}
 
 cs

로직 자체는 틀린게 아닌데, board 다 확인하는것 자체가 너무 비효율적이고 디버깅하기 쉽지 않아서 코드를 버린다. 

 

두번째시도 -> 시간초과

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class swea_5648_원자소멸시뮬레이션2 {
 
    static int totalCase = 0;
    static int howManyAtom =0;
    static int answer = 0;
//    상(0), 하(1), 좌(2), 우(3)
    static int[] dirY = {1,-1,0,0};
    static int[] dirX = {0,0,-1,1};
    static class atomInfo {
        int x;
        int y;
        int dir;
        int energy;
        boolean isAlive;
        atomInfo(int x, int y, int dir, int energy, boolean isAlive){
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.energy = energy;
            this.isAlive = isAlive;
        }
    }
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        totalCase = Integer.parseInt(br.readLine());
        
        
        for(int p=1; p<=totalCase; p++) {
        answer = 0; //init
        howManyAtom = Integer.parseInt(br.readLine());
        atomInfo[] gogoSSing = new atomInfo[howManyAtom];
        for(int i=0; i<howManyAtom; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int xPos = ( Integer.parseInt(st.nextToken()) + 1000 ) * 2;
            int yPos = ( Integer.parseInt(st.nextToken()) + 1000 ) * 2;
            int dir = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            gogoSSing[i] = new atomInfo(xPos, yPos, dir, e, true);
        }//end of for loop
        
        
        out : while(true) {
            //Zero step Make sure all atoms are dead!!!!!! 
            boolean search = false;
            for(int i=0; i<howManyAtom; i++) {
                if(gogoSSing[i].isAlive == true) search = true;
            } if(search == false) break out;
            
            
            //first step 1. Move atom! 
            for(int i=0; i<howManyAtom; i++) {
                int nx = gogoSSing[i].x + dirX[gogoSSing[i].dir];
                int ny = gogoSSing[i].y + dirY[gogoSSing[i].dir];
                
                if(nx < 0 || ny < 0 || nx>4000 || ny>4000) {
                    gogoSSing[i].isAlive = false;
                    continue;
                }
                gogoSSing[i].x = nx;
                gogoSSing[i].y = ny;
            }
            
            //second step 2. How many atoms were crashed?
            for(int i=0; i<howManyAtom; i++) {
                boolean firstLoop = false;
                if(gogoSSing[i].isAlive == false) continue;
                for(int j=0; j<howManyAtom; j++) {
                    if(i==j) continue; 
                    
                    if(gogoSSing[j].isAlive == false) continue;
                
                    if(gogoSSing[i].x == gogoSSing[j].x && gogoSSing[i].y == gogoSSing[j].y) {
                        //crashed!!
                        firstLoop = true;
                        
                        gogoSSing[j].isAlive = false; //death
                        answer += gogoSSing[j].energy;
                    }
                }
                if(firstLoop == true) {
                    answer += gogoSSing[i].energy;
                }//첫번째껏도 돌
            }
            
            //third step 3. renew your ans!! ^_^
        }
        System.out.println("#"+p+" "+answer);
        }
    }
}
 
 cs

시간을 단축할 부분을 찾아봐야 겠다.

'알고리즘' 카테고리의 다른 글

알고리즘80 :: 프로그래머스_베스트앨범  (0) 2020.04.21
알고리즘79 :: BOJ_2503_숫자야구  (0) 2020.04.11
알고리즘77 :: 이분탐색이란? BOJ_13702에 적용  (0) 2020.03.18
알고리즘76 :: BOJ_7576_토마토  (0) 2020.03.11
알고리즘75 :: BOJ_6603_로또  (0) 2020.03.11

티스토리툴바