JUST WRITE IT. HomeArchivesTagsCategories
백준 17143번 낚시왕
|AlgorithmBOJ|

#17143. 낚시왕

문제링크

Problem

  • R x C 크기의 격자판
  • 낚시왕 위치 (0, 0)
  • 1초 동안 일어나는 일
    1. 낚시왕 오른쪽으로 한 칸 이동
      (낚시왕이 먼저 이동하기에 상어가 이동하기 전 잡히게 된다.)
    2. 낚시왕이 열에 있는 상어 중 가장 가까운 상어를 잡는다.
    3. 상어 이동
      상어 : 속도와 크기를 가짐
      경계를 넘게되면 방향을 반대로 바꿈
      이동을 마친 후에 상어가 한 칸에 여러 마리 있으면, 가장 큰 상어가 나머지 상어들을 모두 먹음(사라짐)

Goal: 낚시왕이 잡은 상어 크기의 합

  • 입력

    R : ~100
    C : ~100
    M(상어 수) : ~10000
    r, c : 위치 ~R, ~C
    s : 속력 ~1000
    d : 이동방향 1~4 상하우좌
    z : 크기 ~10000

Solution

  • 필자는 인덱스를 0부터 계산하였기에…이를 모두 신경쓰느라 🐕고생
    그냥 1부터 신경쓰는게 편할 수도 있다. (입력 받을 때도 신경써주어야함…)
  • 상어 정보 (MAX는 100)
    1
    2
    3
    4
    struct INFO {
    	int row, col, speed, direction, size;
    	bool death = false;
    }sharks[MAX*MAX];
    상어의 현재 위치, 방향, 크기, 사라졌는지 유무가 저장된다.
    1
    2
    3
    4
    for(열의 수: 처음부터~열의 끝까지 이동) 
    	catchShark() //  1. 상어를 잡는다
    	moveShark() //   2. 상어가 이동한다.
    	updateMap() //   3. 이동을 마친 상어들 map에 반영(먹히면 사라지도록)
  • catchShark()
    해당 열을 탐색하다가 상어를 발견하면 답에 크기를 더해주고 리턴
  • moveShark()
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    주기 : 2 * (전체 행이나 열의 크기-1)
    // ex 방향 -> 전체 열의 크기: 4, 상어는 (1, 2)에 있다고 가정할 때
    위치:     2  3  2  1  0  1  2  3  2  1  0  1  2  3
    방향:    -> <- <- <- -> -> -> <- <- <- -> -> -> <-
    이동거리: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 

    주기가 2 * 3 = 6으로 이동거리가 6마다 같은 위치를 반복하고 있음
    방향은 0이나 전체 열의 크기-1에 위치할 때 바뀜
    위치는 방향에 맞게 이동해주면 됨

    방향
    1 2 3 4  // 상하 우좌
    1 <-> 2 (1일 때 2, 2일 때 1)
    3 <-> 4 (3일 때 4, 4일 때 3)
    현재 방향을 2로 나눴을 때 
    나머지가 0이면 현재 방향에서 1을 빼주고
    아니면 1을 더해주면 바뀐 방향을 구할 수 있다.
  • updateMap()
  1. map을 초기화 해준다. (이동한 상어의 위치를 새로 반영하기 위해)
  2. 해당 위치에 상어가 있을 때와 없을 때를 구분해서 처리를 해준다.

초기에 입력값을 반영하기 위해, 입력을 모두 받고 한 번 호출해준다.

1 Try

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
#include <cstdio>
#define MAX 100
using namespace std;
int r, c, m, idx, answer;
// 상하우좌
int dx[4] = {-1, 1, 0, 0}; 
int dy[4] = {0, 0, 1, -1};
// 상어 정보
struct INFO {
	int row, col, speed, direction, size;
	bool death = false;
}sharks[MAX*MAX];
int map[MAX][MAX][2]; // 상어가 존재한다면 해당 상어 크기와 해당 상어가 몇 번째 상어인지
void catchShark(int col) {
	for (int i = 0; i < r; ++i) {
		if (map[i][col][0] != 0) {
			sharks[map[i][col][1]].death = true;
			answer += sharks[map[i][col][1]].size;
			return;
		}
	}
}
void changeDirection(int idx) {
	if (sharks[idx].direction % 2 == 0) {
		sharks[idx].direction--;
	}
	else {
		sharks[idx].direction++;
	}
}
void moveShark(int idx, int end) {
	int period = 2 * end;
	int move = sharks[idx].speed % period;
	for (int i = 0; i < move; ++i) {
		if (sharks[idx].direction <= 2) { // 상하
			if ((sharks[idx].row == end && sharks[idx].direction == 2) ||
				(sharks[idx].row == 0 && sharks[idx].direction == 1)) {
				changeDirection(idx);
			}
			sharks[idx].row += dx[sharks[idx].direction - 1];
		}
		else { // 우좌
			if ((sharks[idx].col == end && sharks[idx].direction == 3) ||
				(sharks[idx].col == 0 && sharks[idx].direction == 4)) {
				changeDirection(idx);
			}
			sharks[idx].col += dy[sharks[idx].direction-1];
		}
	}
}
void updateMap() {
	for (int i = 0; i < r; ++i) { // map 초기화
		for (int j = 0; j < c; ++j) {
			map[i][j][0] = 0;
		}
	}
	for (int i = 0; i < m; ++i) {
		if (sharks[i].death) continue;
		int r = sharks[i].row;
		int c = sharks[i].col;
		if (map[r][c][0] != 0) { // 해당 위치에 상어가 있다면
			if (sharks[i].size > map[r][c][0]) {
				sharks[map[r][c][1]].death = true;
				map[r][c][0] = sharks[i].size;
				map[r][c][1] = i;
			}
			else {
				sharks[i].death = true;
			}
		}
		else { // 해당 위치에 상어가 없을 때
			map[r][c][0] = sharks[i].size;
			map[r][c][1] = i;
		}
	}
}

int main() {
	scanf("%d %d %d", &r, &c, &m);
	int row, col;
	for (int i = 0; i < m; ++i) {
		scanf("%d", &row);
		sharks[idx].row = row - 1;
		scanf("%d", &col);
		sharks[idx].col = col - 1;
		scanf("%d", &sharks[idx].speed);
		scanf("%d", &sharks[idx].direction);
		scanf("%d", &sharks[idx++].size);
	}
	updateMap(); // 초기 map update
	for (int i = 0; i < c; ++i) {
		catchShark(i); // 상어 잡기
		for (int j = 0; j < m; ++j) { // 상어 이동
			if (sharks[j].death) continue;
			if (sharks[j].direction <= 2) {
				moveShark(j, r-1);
			}
			else {
				moveShark(j, c-1);
			}
		}
		updateMap(); // 이동한 상어 위치 반영
	}
	printf("%d\n", answer);
	return 0;
}
  • 자꾸 for문에서 i나 j가 아닌 r, c로 고정값을 두어서…이런 실수는 진짜진짜 조심하자.

For Debug

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
#include <cstdio>
#define MAX 100
using namespace std;
int r, c, m, idx, answer;
// 상하우좌
int dx[4] = {-1, 1, 0, 0}; 
int dy[4] = {0, 0, 1, -1};
// 상어 정보
struct INFO {
	int row, col, speed, direction, size;
	bool death = false;
}sharks[MAX*MAX];
int map[MAX][MAX][2]; // 상어가 존재한다면 해당 상어 크기와 해당 상어가 몇 번째 상어인지
void catchShark(int col) {
	/*printf("%d번째\n", col); // map 확인
	for (int i = 0; i < r; ++i) {
		for (int j = 0; j < c; ++j) {
			printf("%d ", map[i][j][0]);
		}
		printf("\n");
	}*/
	for (int i = 0; i < r; ++i) {
		if (map[i][col][0] != 0) {
			sharks[map[i][col][1]].death = true;
			answer += sharks[map[i][col][1]].size;
			return;
		}
	}
}

void changeDirection(int idx) {
	if (sharks[idx].direction % 2 == 0) {
		sharks[idx].direction--;
	}
	else {
		sharks[idx].direction++;
	}
}

void moveShark(int idx, int end) {
	int period = 2 * end;
	int move = sharks[idx].speed % period;
	for (int i = 0; i < move; ++i) {
		if (sharks[idx].direction <= 2) { // 상하
			if ((sharks[idx].row == end && sharks[idx].direction == 2) ||
				(sharks[idx].row == 0 && sharks[idx].direction == 1)) {
				changeDirection(idx);
			}
			sharks[idx].row += dx[sharks[idx].direction - 1];
		}
		else { // 우좌
			if ((sharks[idx].col == end && sharks[idx].direction == 3) ||
				(sharks[idx].col == 0 && sharks[idx].direction == 4)) {
				changeDirection(idx);
			}
			sharks[idx].col += dy[sharks[idx].direction-1];
		}
	}
}

void updateMap() {
	for (int i = 0; i < r; ++i) {
		for (int j = 0; j < c; ++j) {
			map[i][j][0] = 0;
		}
	}
	for (int i = 0; i < m; ++i) {
		if (sharks[i].death) continue;
		int r = sharks[i].row;
		int c = sharks[i].col;
		if (map[r][c][0] != 0) { // 해당 위치에 상어가 있다면
			if (sharks[i].size > map[r][c][0]) {
				sharks[map[r][c][1]].death = true;
				map[r][c][0] = sharks[i].size;
				map[r][c][1] = i;
			}
			else {
				sharks[i].death = true;
			}
		}
		else { // 해당 위치에 상어가 없을 때
			map[r][c][0] = sharks[i].size;
			map[r][c][1] = i;
		}
	}
}

int main() {
	scanf("%d %d %d", &r, &c, &m);
	int row, col;
	for (int i = 0; i < m; ++i) {
		scanf("%d", &row);
		sharks[idx].row = row - 1;
		scanf("%d", &col);
		sharks[idx].col = col - 1;
		scanf("%d", &sharks[idx].speed);
		scanf("%d", &sharks[idx].direction);
		scanf("%d", &sharks[idx++].size);
	}
	updateMap();
	/*for (int i = 0; i < m; ++i) { // 입력 확인
		printf("%d %d %d %d %d\n", sharks[i].row, sharks[i].col, sharks[i].speed, sharks[i].direction, sharks[i].size);
	}*/
	for (int i = 0; i < c; ++i) {
		catchShark(i);
		for (int j = 0; j < m; ++j) {
			if (sharks[j].death) continue;
			if (sharks[j].direction <= 2) {
				moveShark(j, r-1);
			}
			else {
				moveShark(j, c-1);
			}
		}
		updateMap();
	}
	printf("%d\n", answer);
	return 0;
}
Algorithm