Be a developer

백준 17143 낚시왕 본문

sw 역량테스트

백준 17143 낚시왕

중국고대사 2019. 9. 4. 23:31

상반기 코딩 테스트 기출문제이다.

그 때는 미세먼지 문제를 푼다고 읽어보기만 했던 문제였다.

문제 자체는 어렵지 않고, 시간 복잡도를 잘 계산해서 이동 거리를 줄이는 것이 중요한 포인트이다.

 

상어들을 class로 만들어서 arraylist로 저장한 후 먼저 낚시왕에게 잡히는 것들을 계산한다.

 

그리고 상어를 이동하는데, 이 때 거리를 줄이는 법을 생각해내야 했다.

% 연산자로 가능할 것이라 생각했는데, 2 * (r - 1) or 2 * (c - 1)로 연산해야 됨을 찾아 내었다.

하지만 양 끝에서 시작하는 경우, 예를 들어 왼쪽 끝에서 오른쪽 방향을 보고 있는 상어의 경우

해당 연산만큼 % 연산을 한 후 그 값이 0인 경우에는 방향을 바꿔 준 후 이동해야 했다. 이를 빠르게 찾지 못하고 다른 방법들을 생각한다고 시간이 조금 걸렸던 것 같다.

 

그리고 평소에 문제를 풀면서 class를 만들기 귀찮아서 배열로 만들고 arraylist 안에 넣었었는데,

이번 문제는 상어들이 만났을 때 하나만 남기고 없애는 방법이 빠르게 떠오르지 않다가,

상어들을 2차원 배열에 저장하고 같은 위치에 들어오면 덮어 쓰면 된다는 것을 알게 되어,

배열이 아니라 class를 따로 만들어서 arraylist에 넣어주었다.

 

덕분에 시간초과 없이 무사히 통과되었다.

아래는 코드이다.

 

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static int ans;
    static int[] dr = { -1100 };
    static int[] dc = { 001-1 };
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        ArrayList<Shark> sharks = new ArrayList<>();
 
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            // row, col, 속력, 이동 방향, 크기
            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            int speed = Integer.parseInt(st.nextToken());
            int dir = Integer.parseInt(st.nextToken());
            int size = Integer.parseInt(st.nextToken());
            sharks.add(new Shark(row, col, speed, dir, size));
        }
 
        // idx는 낚시왕 위치
        int idx = 0;
        while (idx < c) {
            idx++;// 낚시왕 이동
            // 낚시왕이 상어 잡음
            int minRow = r + 1;
            int minIdx = -1;
            for (int i = 0; i < sharks.size(); i++) {
                if (sharks.get(i).col == idx) {
                    if (sharks.get(i).row < minRow) {
                        minIdx = i;
                        minRow = sharks.get(i).row;
                    }
                }
            }
            if (minIdx != -1) {
                ans += sharks.get(minIdx).size;
                sharks.remove(minIdx);
            }
            // 상어 이동
            for (int i = 0; i < sharks.size(); i++) {
                int row = sharks.get(i).row;
                int col = sharks.get(i).col;
                int speed = sharks.get(i).speed;
                int dir = sharks.get(i).dir;
 
                if (speed == 0)
                    continue;
                int togo = 0;
                if (dir == 3 || dir == 4) {
                    togo = speed % ((c - 1* 2);
                    if (col == 1 && dir == 3 || col == c && dir == 4) {// 끝에서 안쪽 방향
                        if (dir == 3)
                            dir = 4;
                        else
                            dir = 3;
                    }
                    for (int j = 0; j < togo; j++) {
                        col += dc[dir - 1];
                        if (col == 0) {
                            dir = 3;
                            col = 2;
                        } else if (col == c + 1) {
                            dir = 4;
                            col = c - 1;
                        }
                    }
                } else {
                    togo = speed % ((r - 1* 2);
                    if (row == 1 && dir == 2 || row == r && dir == 1) {
                        if (dir == 2)
                            dir = 1;
                        else
                            dir = 2;
                    }
 
                    for (int j = 0; j < togo; j++) {
                        row += dr[dir - 1];
                        if (row == 0) {
                            dir = 2;
                            row = 2;
                        } else if (row == r + 1) {
                            dir = 1;
                            row = r - 1;
                        }
                    }
                }
                sharks.get(i).row = row;
                sharks.get(i).col = col;
                sharks.get(i).dir = dir;
            } // 상어 이동
            Shark[][] map = new Shark[r + 1][c + 1];
            for (int j = 0; j < sharks.size(); j++) {
                int row = sharks.get(j).row;
                int col = sharks.get(j).col;
                int size = sharks.get(j).size;
 
                if (map[row][col] == null)
                    map[row][col] = sharks.get(j);
                else if (map[row][col].size < sharks.get(j).size) {
                    map[row][col] = sharks.get(j);
                }
            }
            sharks.clear();
            for (int x = 1; x <= r; x++) {
                for (int y = 1; y <= c; y++) {
                    if (map[x][y] != null) {
                        sharks.add(map[x][y]);
//                        System.out.println(map[x][y].row + " " + map[x][y].col + " " + map[x][y].speed + " "
//                                + map[x][y].dir + " " + map[x][y].size);
                    }
                }
            }
//            System.out.println();
 
        } // 낚시왕 이동
        System.out.println(ans);
    }
 
    static class Shark {
        int row;
        int col;
        int speed;
        int dir;
        int size;
 
        public Shark(int row, int col, int speed, int dir, int size) {
            super();
            this.row = row;
            this.col = col;
            this.speed = speed;
            this.dir = dir;
            this.size = size;
        }
 
    }
}
cs

-----------------------------------------------------------------------------------------------------------------------------------맵의 끝에서 시작하는 친구들을 따로 분리해서 처리를 해줬는데, 다시 보니 어짜피 1칸 움직이면 같아지기 때문에 해당 코드를 삭제 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static int ans;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, 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());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        ArrayList<Shark> sharks = new ArrayList<>();
 
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            // row, col, 속력, 이동 방향, 크기
            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            int speed = Integer.parseInt(st.nextToken());
            int dir = Integer.parseInt(st.nextToken());
            int size = Integer.parseInt(st.nextToken());
            sharks.add(new Shark(row, col, speed, dir, size));
        }
 
        // idx는 낚시왕 위치
        int idx = 0;
        while (idx < c) {
            idx++;// 낚시왕 이동
            // 낚시왕이 상어 잡음
            int minRow = r + 1;
            int minIdx = -1;
            for (int i = 0; i < sharks.size(); i++) {
                if (sharks.get(i).col == idx) {
                    if (sharks.get(i).row < minRow) {
                        minIdx = i;
                        minRow = sharks.get(i).row;
                    }
                }
            }
            if (minIdx != -1) {
                ans += sharks.get(minIdx).size;
                sharks.remove(minIdx);
            }
            // 상어 이동
            for (int i = 0; i < sharks.size(); i++) {
                int row = sharks.get(i).row;
                int col = sharks.get(i).col;
                int speed = sharks.get(i).speed;
                int dir = sharks.get(i).dir;
 
                if (speed == 0)
                    continue;
                int togo = 0;
                if (dir == 3 || dir == 4) {
                    togo = speed % ((c - 1) * 2);

                    for (int j = 0; j < togo; j++) {
                        col += dc[dir - 1];
                        if (col == 0) {
                            dir = 3;
                            col = 2;
                        } else if (col == c + 1) {
                            dir = 4;
                            col = c - 1;
                        }
                    }
                } else {
                    togo = speed % ((r - 1) * 2);
 
                    for (int j = 0; j < togo; j++) {
                        row += dr[dir - 1];
                        if (row == 0) {
                            dir = 2;
                            row = 2;
                        } else if (row == r + 1) {
                            dir = 1;
                            row = r - 1;
                        }
                    }
                }
                sharks.get(i).row = row;
                sharks.get(i).col = col;
                sharks.get(i).dir = dir;
            } // 상어 이동
            Shark[][] map = new Shark[r + 1][c + 1];
            for (int j = 0; j < sharks.size(); j++) {
                int row = sharks.get(j).row;
                int col = sharks.get(j).col;
                int size = sharks.get(j).size;
 
                if (map[row][col] == null)
                    map[row][col] = sharks.get(j);
                else if (map[row][col].size < sharks.get(j).size) {
                    map[row][col] = sharks.get(j);
                }
            }
            sharks.clear();
            for (int x = 1; x <= r; x++) {
                for (int y = 1; y <= c; y++) {
                    if (map[x][y] != null) {
                        sharks.add(map[x][y]);
//                        System.out.println(map[x][y].row + " " + map[x][y].col + " " + map[x][y].speed + " "
//                                + map[x][y].dir + " " + map[x][y].size);
                    }
                }
            }
//            System.out.println();
 
        } // 낚시왕 이동
        System.out.println(ans);
    }
 
    static class Shark {
        int row;
        int col;
        int speed;
        int dir;
        int size;
 
        public Shark(int row, int col, int speed, int dir, int size) {
            super();
            this.row = row;
            this.col = col;
            this.speed = speed;
            this.dir = dir;
            this.size = size;
        }
 
    }
}

'sw 역량테스트' 카테고리의 다른 글

백준 17136 색종이 붙이기  (0) 2019.09.21
백준 17144 미세먼지 안녕!  (0) 2019.09.04
백준 14502 연구소  (0) 2019.08.21
백준 12100 2048  (0) 2019.08.15
백준 13460 구슬 탈출2  (2) 2019.08.13
Comments