반응형

https://www.acmicpc.net/problem/17143

 

17143번: 낚시왕

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.

www.acmicpc.net

 

[ 문제풀이 ]

 

처음에 풀이 방법을 떠올리기까지 30분 정도 걸린 것 같습니다.

 

먼저 상어의 속도와 관련해서 일정 속도 이상이면 제자리에 여러 번 도착한다는 것을 알았습니다. 그렇다면 제자리로 오기까지의 속도는 시뮬레이션 결과에 큰 영향을 미치지 않는다고 생각을 했고, 제자리에 오는 데 걸리는 시간으로 속도를 나누어 주었습니다. 그리고 속도를 그 나머지 값으로 경신해주었습니다.

위의 그림을 보면 총 이동거리 10일 때 제자리로 돌아온다는 것을 알 수 있습니다. 바로 총 거리 - 1을 두 배 해준 값이 됩니다. 따라서 모든 상어의 속도 s를 (총 거리 - 1) * 2로 나눈 나머지 값으로 경신시켜줍니다. 그렇게 되면 시뮬레이션 시간도 대폭 감소될 것이고 시간제한도 피할 수 있을 것입니다.

 

이후 시뮬레이션을 통해 상어들을 이동시켜 주었고, visited배열을 통해서 미리 도착해 있던 상어가 있다면 크기 비교 후 더 작다면 없애고, 더 크다면 방금 도착한 상어를 없애주는 방법으로 구현하였습니다.

 

 

[ 소스 코드 ]

 

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
#include <iostream>
#include <cstring>
 
using namespace std;
 
struct shark {
    int r;
    int c;
    int s;
    int d;
    int z;
};
 
int R, C, M;
shark arr[10001];                    //각 상어의 정보를 저장발 배열
int dr[5] = { 0,-1,1,0,0 };            //방향 배열
int dc[5] = { 0,0,0,1,-1 };
int visited[101][101];                //상어가 도착한 장소에 상어가 있는지 체크하기 위한 배열
 
int main()
{
    cin >> R >> C >> M;
    int idx = 1;
    int sum = 0;
 
    for (int i = 1; i <= M; i++) {
        int r, c, s, d, z;
        scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
        if (d < 3) {                //일정 속도 이상이면 여러번 제자리로 돌아오기 때문에
            s %= 2 * (R - 1);        //총 (길이-1)*2로 나눈 나머지 값을 속도에 넣어준다.
        }
        else {
            s %= 2 * (C - 1);
        }
        arr[i] = { r,c,s,d,z };
    }
 
    while (idx <= C)
    {
        memset(visited, 0, sizeof(visited));
        int min = 999;
        int x = 987654321;
        for (int i = 1; i <= M; i++) {        //현재 사람과 같은 위치에 있는 상어 중
            if (arr[i].r == 0) continue;    //가장 땅에 가까운 상어의 번호를 x에 저장
            if (idx == arr[i].c) {
                if (min > arr[i].r) {
                    min = arr[i].r;
                    x = i;
                }
            }
        }
        if (x != 987654321) {                //x가 경신 되었다면 그 상어를 없애고
            sum += arr[x].z;                //sum에 크기를 더해준다.
            arr[x] = { 0 };
        }
 
        for (int i = 1; i <= M; i++) {        //모든 상어를 움직인다.
            if (arr[i].r == 0) continue;
            int rr = arr[i].r;
            int cc = arr[i].c;
            for (int j = 0; j < arr[i].s; j++) {
                rr += dr[arr[i].d];
                cc += dc[arr[i].d];
                if (arr[i].d == 1) {
                    if (rr == 1) {
                        arr[i].d = 2;
                    }
                    else if (rr < 1) {
                        arr[i].d = 2;
                        rr = 2;
                    }
                }
                else if (arr[i].d == 2) {
                    if (rr == R) {
                        arr[i].d = 1;
                    }
                    else if (rr > R) {
                        rr = R - 1;
                        arr[i].d = 1;
                    }
                }
                else if (arr[i].d == 3) {
                    if (cc == C) {
                        arr[i].d = 4;
                    }
                    else if (cc > C) {
                        cc = C - 1;
                        arr[i].d = 4;
                    }
                }
                else if (arr[i].d == 4) {
                    if (cc == 1) {
                        arr[i].d = 3;
                    }
                    else if (cc < 1) {
                        arr[i].d = 3;
                        cc = 2;
                    }
                }
            }
            if (visited[rr][cc] == 0) {        //만약 처음 상어가 도착했다면
                visited[rr][cc] = i;        //visited배열에 상어 번호를 저장
                arr[i].r = rr;
                arr[i].c = cc;
            }
            else {                            //이미 와 있던 상어가 있다면
                if (arr[i].z > arr[visited[rr][cc]].z) {
                    arr[visited[rr][cc]] = { 0 };
                    visited[rr][cc] = i;    //크기를 비교 후 더 크면
                    arr[i].r = rr;            //visited배열을 경신해준다
                    arr[i].c = cc;
                }
                else {
                    arr[i] = { 0 };            //더 작다면 더 작은 상어를 없앤다.
                }
            }
        }
        idx++;                //오른쪽으로 옮긴다.
    }
 
    cout << sum;        //결과 출력
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24
[ 백준 ] 16946번 - 벽 부수고 이동하기 4 (C++)  (0) 2022.05.22
[ 백준 ] 12100번 - 2048(Easy) (C++)  (0) 2022.05.21
반응형

 

https://www.acmicpc.net/problem/12100

 

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net

 

문제의 조건

[ 문제풀이 ]

구현 방법은 그렇게 어렵지는 않았으나 생각보다 까다로운 문제였습니다. 

 

먼저 합쳐야 하는 숫자들을 판단해야 했습니다. 합쳐지는 숫자들은 한쪽 방향으로 움직였을 때 충돌하는 숫자와 같은 값을 가져야 했고, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다는 조건이 있었습니다.

 

이러한 조건을 만족하기 위해서 방향을 정해 움직였을 때 어떠한 결과가 나오는지 구현할 수 있는 함수를 먼저 만들었습니다.

위와 같은 상황에서 위로 블록을 이동시키면 다음과 같은 결과가 나옵니다.

4와 4는 같은 숫자이지만 합쳐지지 않았는데, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다는 조건 때문입니다.

 

그렇다면 이를 어떤 식으로 구현해야 할까요?

 

블록을 움직일 방향이 왼쪽일 때를 예로 들면 왼쪽에 있는 블록부터 합쳐지기 때문에 왼쪽부터 오른쪽으로 배열을 탐색하면서 오른쪽에 있는 블록이 나와 같은 값을 가지고 있는지 체크하고, 같다면 합치고, 같지 않다면 그대로 두는 방법으로 구현했습니다.

 

그리고 합치는 과정을 모두 거친 후 모든 블록들을 왼쪽으로 밀어야 했는데 배열을 왼쪽부터 오른쪽으로 탐색하며 0이 아닌 숫자를 만나면 제일 왼쪽 칸부터 차곡차곡 쌓아주는 방식으로 구현했습니다.

 

하지만 여기서 문제가 발생했는데, 4방향을 모두 구현하기 위해서는 함수가 매우 길어질 것이라고 생각했습니다.

 

함수가 길어지면 실수를 할 수도 있고, 디버깅을 할 때도 쉽지 않을 것이라고 생각이 들어서 배열을 90도씩 돌리면서 한쪽으로 밀면 네 방향으로 움직일 수 있을 것이라고 생각했습니다.

 

마지막으로 재귀 함수를 통해서 최댓값을 구했습니다.

 

백트래킹을 위해서 temp라는 배열을 만들고 temp배열에 arr를 저장하고 재귀함수를 빠져나올 때 arr에 다시 temp를 저장하는 방식으로 구현했습니다.

 

만약 5번을 다 움직였다면 arr배열을 모두 탐색하며 가장 큰 숫자를 ans에 넣었고, ans를 출력했습니다.

 

[ 소스 코드 ]

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
#include <iostream>
 
using namespace std;
 
int N;
int arr[21][21];
int ans = 0;
 
void move()                                                //블럭들을 합치고 옮기는 함수
{
    for (int i = 0; i < N; i++) {
        int before = 0;
        int y;
        int x;
        for (int j = 0; j < N; j++) {
            if (before == 0) {                            //왼쪽 블럭이 합쳐지지 않았을 때
                if (arr[i][j] != 0) {                    //빈 블럭이 아니라면
                    before = arr[i][j];                    //합쳐질 블럭과 비교하기 위해 before 변수에 값을 넣어준다.
                    y = i;                                //비교를 위해 좌표를 저장
                    x = j;
                }
            }
            else {
                if (arr[i][j] != 0) {                    //왼쪽에 블럭이 있다면
                    if (before == arr[i][j]) {            //충돌하는 블럭의 값이 같다면
                        arr[y][x] = before * 2;            //블럭의 값을 2배로 바꿔주고
                        arr[i][j] = 0;                    //충돌한 블럭을 제거
                        before = 0;                        //before을 0으로 초기화 시켜준다.
                    }
                    else {                                //만약 값이 다르다면
                        before = arr[i][j];                //before을 지금 좌표의 값으로 바꿔주고
                        y = i;                            //좌표를 저장한다.
                        x = j;
                    }
                }
            }
        }
    }
    for (int i = 0; i < N; i++) {                        //합치는 과정이 끝나면
        int cnt = 0;
        for (int j = 0; j < N; j++) {                    //왼쪽에서부터 차례로
            if (arr[i][j] != 0) {                        //빈 블럭이 아니라면
                if (cnt != j) {                            //왼쪽에 빈 공간이 있다면
                    arr[i][cnt] = arr[i][j];            //왼쪽으로 옮기고
                    arr[i][j] = 0;                        //지금 칸을 비워준다.
                }
            cnt++;                                        //비어 있는 칸을 오른쪽으로 한칸씩 옮겨준다.
            }
        }
    }
}
 
void turn(int num)                                        //num만큼 90도 회전
{
    int temp[21][21];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    for (int k = 0; k < num; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                arr[i][j] = temp[j][N - i - 1];
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                temp[i][j] = arr[i][j];
            }
        }
    }
}
 
void dfs(int level)
{
    if (level == 5) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] > ans) {
                    ans = arr[i][j];
                }
            }
        }
        return;
    }
 
    int temp[21][21];                                    //백트래킹을 위해 temp배열 선언
 
    for (int i = 0; i < N; i++) {                        //지금 모습을 temp에 저장
        for (int j = 0; j < N; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    for (int k = 0; k < 4; k++) {
        turn(k);
        move();                                            //옮긴 후
        dfs(level + 1);                                    //다음으로 넘어갔다가
        for (int i = 0; i < N; i++) {                    //나올 때 원상 복구
            for (int j = 0; j < N; j++) {
                arr[i][j] = temp[i][j];
            }
        }
    }
}
 
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
 
    dfs(0);
 
    cout << ans;
}
cs
반응형
저작자표시

'백준' 카테고리의 다른 글

[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24
[ 백준 ] 17143번 - 낚시왕 (C++)  (0) 2022.05.23
[ 백준 ] 16946번 - 벽 부수고 이동하기 4 (C++)  (0) 2022.05.22

+ Recent posts

티스토리툴바