728x90
반응형
https://www.acmicpc.net/problem/17143
17143번: 낚시왕
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.
www.acmicpc.net
최종 코드
GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음
백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ17143
//
// Created by 최화연 on 2022/04/28.
//
#include <iostream>
#include <queue>
using namespace std;
int R, C, M;
struct Shark {
int r;
int c;
int s;
int d;
int z = 0;
};
struct cmp {
bool operator() (Shark s1, Shark s2) {
return s1.z < s2.z;
}
};
Shark shark;
int dr[5] = {0, -1, 1, 0, 0};
int dc[5] = {0, 0, 0, 1, -1};
int opposite[5] = {0, 2, 1, 4, 3};
Shark board[101][101];
int sum_shark_size = 0;
void fishing() {
int c = 0;
while (c < C) {
//1. 낚시왕 한 칸 이동
c ++;
//2. 상어 잡기
for (int r=1; r<=R; r++) {
if (board[r][c].z > 0) {
sum_shark_size += board[r][c].z;
board[r][c].z = 0;
break;
}
}
//3. 상어 이동
priority_queue<Shark, vector<Shark>, cmp> pq;
for (int r=1; r<=R; r++) {
for (int c=1; c<=C; c++) {
if (board[r][c].z == 0) continue;
shark = board[r][c];
board[r][c].z = 0;
if (shark.d == 2) {
int n = R - shark.r;
if (shark.s <= n) {
shark.r += dr[shark.d]*shark.s;
}
else {
shark.r = R;
int q, m;
q = (shark.s-n) / (R-1);
m = (shark.s-n) % (R-1);
if (q % 2 == 1) {
shark.d = 1;
shark.r = 1;
}
for (int i=0; i<m; i++) {
shark.r += dr[shark.d];
if (shark.r < 1 || shark.r > R) {
shark.r -= dr[shark.d];
shark.d = opposite[shark.d];
shark.r += dr[shark.d];
}
}
}
}
else if (shark.d == 1) {
int n = shark.r - 1;
if (shark.s <= n) {
shark.r += dr[shark.d]*shark.s;
}
else {
shark.r = 1;
int q, m;
q = (shark.s-n) / (R-1);
m = (shark.s-n) % (R-1);
if (q % 2 == 1) {
shark.d = 2;
shark.r = R;
}
for (int i=0; i<m; i++) {
shark.r += dr[shark.d];
if (shark.r < 1 || shark.r > R) {
shark.r -= dr[shark.d];
shark.d = opposite[shark.d];
shark.r += dr[shark.d];
}
}
}
}
else if (shark.d == 3) {
int n = C - shark.c;
if (shark.s <= n) {
shark.c += dc[shark.d]*shark.s;
}
else {
shark.c = C;
int q, m;
q = (shark.s-n) / (C-1);
m = (shark.s-n) % (C-1);
if (q % 2 == 1) {
shark.d = 4;
shark.c = 1;
}
for (int i=0; i<m; i++) {
shark.c += dc[shark.d];
if (shark.c < 1 || shark.c > C) {
shark.c -= dc[shark.d];
shark.d = opposite[shark.d];
shark.c += dc[shark.d];
}
}
}
}
else if (shark.d == 4) {
int n = shark.c - 1;
if (shark.s <= n) {
shark.c += dc[shark.d]*shark.s;
}
else {
shark.c = 1;
int q, m;
q = (shark.s-n) / (C-1);
m = (shark.s-n) % (C-1);
if (q % 2 == 1) {
shark.d = 3;
shark.c = C;
}
for (int i=0; i<m; i++) {
shark.c += dc[shark.d];
if (shark.c < 1 || shark.c > C) {
shark.c -= dc[shark.d];
shark.d = opposite[shark.d];
shark.c += dc[shark.d];
}
}
}
}
pq.push(shark);
}
}
while (!pq.empty()) {
shark = pq.top();
pq.pop();
if (board[shark.r][shark.c].z > 0) continue;
board[shark.r][shark.c] = shark;
}
}
}
int main(int argc, const char * argv[]) {
cin >> R >> C >> M;
for (int m=0; m<M; m++) {
cin >> shark.r >> shark.c >> shark.s >> shark.d >> shark.z;
board[shark.r][shark.c] = shark;
}
fishing();
cout << sum_shark_size << endl;
return 0;
}풀이 과정
풀이 시간 1시간 20분
#include <iostream>
#include <queue>
using namespace std;
int R, C, M;
struct Shark {
int r;
int c;
int s;
int d;
int z = 0;
};
struct cmp {
bool operator() (Shark s1, Shark s2) {
return s1.z < s2.z;
}
};
Shark shark;
int dr[5] = {0, -1, 1, 0, 0};
int dc[5] = {0, 0, 0, 1, -1};
int opposite[5] = {0, 2, 1, 4, 3};
Shark board[101][101];
int sum_shark_size = 0;
void fishing() {
int c = 0;
while (c < C) {
//1. 낚시왕 한 칸 이동
c ++;
//2. 상어 잡기
for (int r=1; r<=R; r++) {
if (board[r][c].z > 0) {
sum_shark_size += board[r][c].z;
board[r][c].z = 0;
break;
}
}
//3. 상어 이동
priority_queue<Shark, vector<Shark>, cmp> pq;
for (int r=1; r<=R; r++) {
for (int c=1; c<=C; c++) {
if (board[r][c].z == 0) continue;
shark = board[r][c];
board[r][c].z = 0;
if (shark.d == 2) {
int n = R - shark.r;
if (shark.s <= n) {
shark.r += dr[shark.d]*shark.s;
}
else {
shark.r = R;
int q, m;
q = (shark.s-n) / (R-1);
m = (shark.s-n) % (R-1);
if (q % 2 == 1) {
shark.d = 1;
shark.r = 1;
}
for (int i=0; i<m; i++) {
shark.r += dr[shark.d];
if (shark.r < 1 || shark.r > R) {
shark.r -= dr[shark.d];
shark.d = opposite[shark.d];
shark.r += dr[shark.d];
}
}
}
}
else if (shark.d == 1) {
int n = shark.r - 1;
if (shark.s <= n) {
shark.r += dr[shark.d]*shark.s;
}
else {
shark.r = 1;
int q, m;
q = (shark.s-n) / (R-1);
m = (shark.s-n) % (R-1);
if (q % 2 == 1) {
shark.d = 2;
shark.r = R;
}
for (int i=0; i<m; i++) {
shark.r += dr[shark.d];
if (shark.r < 1 || shark.r > R) {
shark.r -= dr[shark.d];
shark.d = opposite[shark.d];
shark.r += dr[shark.d];
}
}
}
}
else if (shark.d == 3) {
int n = C - shark.c;
if (shark.s <= n) {
shark.c += dc[shark.d]*shark.s;
}
else {
shark.c = C;
int q, m;
q = (shark.s-n) / (C-1);
m = (shark.s-n) % (C-1);
if (q % 2 == 1) {
shark.d = 4;
shark.c = 1;
}
for (int i=0; i<m; i++) {
shark.c += dc[shark.d];
if (shark.c < 1 || shark.c > C) {
shark.c -= dc[shark.d];
shark.d = opposite[shark.d];
shark.c += dc[shark.d];
}
}
}
}
else if (shark.d == 4) {
int n = shark.c - 1;
if (shark.s <= n) {
shark.c += dc[shark.d]*shark.s;
}
else {
shark.c = 1;
int q, m;
q = (shark.s-n) / (C-1);
m = (shark.s-n) % (C-1);
if (q % 2 == 1) {
shark.d = 3;
shark.c = C;
}
for (int i=0; i<m; i++) {
shark.c += dc[shark.d];
if (shark.c < 1 || shark.c > C) {
shark.c -= dc[shark.d];
shark.d = opposite[shark.d];
shark.c += dc[shark.d];
}
}
}
}
pq.push(shark);
}
}
while (!pq.empty()) {
shark = pq.top();
pq.pop();
if (board[shark.r][shark.c].z > 0) continue;
board[shark.r][shark.c] = shark;
}
}
}
int main(int argc, const char * argv[]) {
cin >> R >> C >> M;
for (int m=0; m<M; m++) {
cin >> shark.r >> shark.c >> shark.s >> shark.d >> shark.z;
board[shark.r][shark.c] = shark;
}
fishing();
cout << sum_shark_size << endl;
return 0;
}이전 풀이
풀이 시간 1시간 50분
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
int R, C, M;
//board[r][c] = 해당 칸에 있는 상어 크기
int board[100][100] = {0,};
//0-상, 1-하, 2-우, 4-좌
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
//낚시킹의 위치(열)
int fisher_king = -1;
//낚시킹이 잡은 상어 크기의 합
int cnt = 0;
struct Shark{
int r;
int c;
int s;
int d;
int z;
};
Shark shark;
//격자판에 있는 상어들을 담는 벡터
vector<Shark> sharks;
//상어 이동 때 사용하는 벡터
vector<Shark> cp_sharks;
//다른 상어에 의해 잡아 먹힌 상어 크기를 담는 벡터
vector<int> dead_sharks;
//상어 이동을 하는 함수
Shark move_shark(Shark shark){
//이동 후의 상어 상태를 담을 nshark, 속력과 크기는 변하지 않는다
Shark nshark;
nshark.s = shark.s;
nshark.z = shark.z;
//행 이동
if(shark.d == 0 || shark.d == 1){
int nr = shark.r+shark.s*dy[shark.d];
while(nr < 0 || nr >= R){
if(nr < 0){
shark.s -= (shark.r+1);
shark.r = 1;
shark.d = 1;
nr = shark.r+shark.s*dy[shark.d];
}
else if(nr >= R){
shark.s -= (R-shark.r);
shark.r = R-2;
shark.d = 0;
nr = shark.r+shark.s*dy[shark.d];
}
}
nshark.r = nr;
nshark.c = shark.c;
nshark.d = shark.d;
}
//열 이동
else{
int nc = shark.c+shark.s*dx[shark.d];
while(nc < 0 || nc >= C){
if(nc < 0){
shark.s -= (shark.c+1);
shark.c = 1;
shark.d = 2;
nc = shark.c+shark.s*dx[shark.d];
}
else if(nc >= C){
shark.s -= (C-shark.c);
shark.c = C-2;
shark.d = 3;
nc = shark.c+shark.s*dx[shark.d];
}
}
nshark.r = shark.r;
nshark.c = nc;
nshark.d = shark.d;
}
return nshark;
}
void fish(){
//낚시 킹이 C-1에서 낚시를 할 때까지 반복한다
while(fisher_king < C-1){
//1. move fisher_king
fisher_king++;
//2. fish shark
//잡힌 상어 크기를 담는 변수
int caught = 0;
//땅에서 가까운 상어를 잡기 위해 0부터 탐색한다
for(int r=0; r<R; r++){
//잡을 상어가 있는 경우, 상어를 잡는다
if(board[r][fisher_king] != 0){
cnt += board[r][fisher_king];
//잡힌 상어 크기를 caught에 담아주고, 해당 격자판의 칸을 0으로 바꿔준다
caught = board[r][fisher_king];
board[r][fisher_king] = 0;
break;
}
}
//3. move sharks
//상어를 옮긴 상태로 격자판을 만들어 주기 위해 격자판을 초기화한다
memset(board, 0, sizeof(board));
//기존 상어들의 상태가 당긴 sharks를 cp_sharks에 담아주고, 새로운 상어 상태를 저장하기 위해 sharks를 비운다
cp_sharks = sharks;
sharks.clear();
dead_sharks.clear();
while(!cp_sharks.empty()){
shark = cp_sharks.back();
cp_sharks.pop_back();
//해당 상어가 낚시킹에게 잡힌 상어인 경우, 상어를 이동시키지 않고 없애준다
if(shark.z == caught) continue;
//이동 후의 상어 상태를 shark에 받아온다
shark = move_shark(shark);
//현재 상어의 위치에 다른 상어가 없거나, 더 작은 상어가 있는 경우, 현재 상어를 격자판에 위치시킨다
if(board[shark.r][shark.c] < shark.z){
//다른 상어가 있는 경우, 해당 상어를 잡아먹는다
if(board[shark.r][shark.c] > 0){
dead_sharks.push_back(board[shark.r][shark.c]);
}
board[shark.r][shark.c] = shark.z;
//이동한 상어를 sharks에 추가한다
sharks.push_back(shark);
}
}
//sharks 안에 죽은 상어를 없애준다 -> 상어 이동 후 최종 상어들의 상태를 cp_sharks에 담는다
for(int i=0; i<sharks.size(); i++){
bool ck = true;
for(int j=0; j<dead_sharks.size(); j++){
if(sharks[i].z == dead_sharks[j]){
ck = false;
break;
}
}
if(ck) cp_sharks.push_back(sharks[i]);
}
//sharks를 cp_sharks로 바꿔준다
sharks = cp_sharks;
}
}
int main(int argc, const char * argv[]) {
cin >> R >> C >> M;
for(int i=0; i<M; i++){
cin >> shark.r >> shark.c >> shark.s >> shark.d >> shark.z;
//r,c,d를 각각 1씩 빼준다
shark.r--;
shark.c--;
shark.d--;
sharks.push_back(shark);
board[shark.r][shark.c] = shark.z;
}
//상어가 0마리인 경우, 0 출력 후 종료
if(M == 0){
cout << 0 << endl;
return 0;
}
//낚시 시작
fish();
cout << cnt << endl;
return 0;
}
//시간복잡도 = O(M), 공간복잡도 = O(M)오답 노트
코드 작성만 1시간 50분이 걸렸다. 그런데 제출하자마자 틀렸습니다가 나왔다....
게시판에서 보이는 모든 반례들을 테스트한 결과 모두 정답이었다.
그래서 문제 예제들을 돌리면서 디버깅했는데도 문제를 찾지 못했다.
문제는 sharks 안에 죽은 상어가 있는지 판단하는 과정에서 인덱스 i, j를 헷갈려서였다...
//sharks 안에 죽은 상어를 없애준다 -> 상어 이동 후 최종 상어들의 상태를 cp_sharks에 담는다
for(int i=0; i<sharks.size(); i++){
bool ck = true;
for(int j=0; j<dead_sharks.size(); j++){
//문제의 구간 수정 전 -> if(sharks[i].z == dead_sharks[i])
if(sharks[i].z == dead_sharks[j]){
ck = false;
break;
}
}
if(ck) cp_sharks.push_back(sharks[i]);
}j를 넣었어야했는데 i를 넣었으니 당연히 오류가 난다.
그치만 그많은 반례들을 피해갔다는 것도 참 신기하다,,,(어찌됐든 내가 실수한거고 내 탓을 할 수 밖에,,ㅠ)
우리는 인덱스를 나타낼 때 i, j, k를 많이 쓴다,, 이게 습관이 돼버렸는데 i와 j가 비슷하니 이와 같은 실수를 하게 된 것이다.
좀더 가시적으로 알아볼 수 있게 다른 변수를 사용하거나, 실수하지 않도록 코드를 작성해야겠다!
728x90
반응형
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 7453 합이 0인 네 정수 Python 3 (0) | 2021.10.05 |
|---|---|
| 백준 17837 새로운 게임 2 C++ (0) | 2021.10.05 |
| 백준 16472 고냥이 Python3 (0) | 2021.10.04 |
| 백준 3649 로봇 프로젝트 Python3 (0) | 2021.10.04 |
| 백준 19237 어른 상어 C++ (4) | 2021.10.04 |