728x90
반응형
https://www.acmicpc.net/problem/19237
19237번: 어른 상어
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미
www.acmicpc.net
최종 코드
GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음
백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ19237_1
//
// Created by Hwayeon on 2021/10/19.
//
#include <iostream>
#include <deque>
using namespace std;
int N, M, k;
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, -1, 1, 0, 0};
struct Shark{
int num;
int x;
int y;
int d;
int priority[5][4] = {0, };
};
//board[y][x]= {shark_num, smell_timer}
int board[20][20][2] = {0, };
deque<Shark> sharks;
deque<Shark> copy_sharks;
int sec = 0;
void move_sharks(){
while(sharks.size() > 1){
if(sec >= 1000){
sec = -1;
break;
}
//1. 상어 이동 방향 정하기
while(!sharks.empty()){
Shark now_shark = sharks.front();
sharks.pop_front();
bool check = false;
for(int d=0; d<4; d++){
int nd = now_shark.priority[now_shark.d][d];
int nx = now_shark.x + dx[nd];
int ny = now_shark.y + dy[nd];
if(nx<0 || nx>=N || ny<0 || ny>=N) continue;
if(board[ny][nx][0] == 0){
check = true;
now_shark.x = nx;
now_shark.y = ny;
now_shark.d = nd;
break;
}
}
if(check) {
copy_sharks.push_back(now_shark);
continue;
}
//자신의 냄새가 있는칸으로
for(int d=0; d<4; d++){
int nd = now_shark.priority[now_shark.d][d];
int nx = now_shark.x + dx[nd];
int ny = now_shark.y + dy[nd];
if(nx<0 || nx>=N || ny<0 || ny>=N) continue;
if(board[ny][nx][0] == now_shark.num){
now_shark.x = nx;
now_shark.y = ny;
now_shark.d = nd;
break;
}
}
copy_sharks.push_back(now_shark);
}
//2. 냄새 타이머 가동
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
if(board[y][x][0] == 0) continue;
board[y][x][1]--;
if(board[y][x][1] == 0) board[y][x][0] = 0;
}
}
//3. 이동하기
while(!copy_sharks.empty()){
Shark now_shark = copy_sharks.front();
copy_sharks.pop_front();
if(board[now_shark.y][now_shark.x][0] == 0 || board[now_shark.y][now_shark.x][0] == now_shark.num){
board[now_shark.y][now_shark.x][0] = now_shark.num;
board[now_shark.y][now_shark.x][1] = k;
sharks.push_back(now_shark);
}
}
sec++;
}
}
int main(int argc, const char * argv[]) {
cin >> N >> M >> k;
for(int i=0; i<M; i++){
Shark shark;
shark.num = i+1;
sharks.push_back(shark);
}
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
cin >> board[y][x][0];
if(board[y][x][0] > 0){
sharks[board[y][x][0]-1].x = x;
sharks[board[y][x][0]-1].y = y;
board[y][x][1] = k;
}
}
}
for(int i=0; i<M; i++){
cin >> sharks[i].d;
}
for(int i=0; i<M; i++){
for(int d=1; d<=4; d++){
for(int j=0; j<4; j++){
cin >> sharks[i].priority[d][j];
}
}
}
move_sharks();
cout << sec << endl;
return 0;
}풀이 과정
풀이 시간 1시간 27분
#include <iostream>
#include <deque>
using namespace std;
int N, M, k;
//1-상, 2-하, 3-좌, 4-우
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, -1, 1, 0, 0};
struct Shark{
//상어 번호
int num;
//상어 위치
int x;
int y;
//상어가 바라보는 방향
int d;
//priority[d] = d 방향에서 1~4번째 우선순위
int priority[5][4] = {0, };
};
//board[y][x][0] = 냄새를 뿌린 상어의 번호(0인 경우 냄새가 없는 상태), board[y][x][1] = 냄새 타이머
int board[20][20][2] = {0, };
//격자 안의 상어들을 담는 덱
deque<Shark> sharks;
//이동한 상어들을 담는 덱
deque<Shark> copy_sharks;
int sec = 0;
void move_sharks(){
//1번 상어만 남을 때까지 while문 반복
while(sharks.size() > 1){
//1,000초가 넘었는데 다른 상어가 격자에 있는 경우, while문을 빠져나온다
if(sec >= 1000){
sec = -1;
break;
}
//1. 상어 이동 방향 정하기 - 번호가 작은 상어부터 이동 방향을 정하고 차례대로 copy_sharks에 담는다
while(!sharks.empty()){
Shark now_shark = sharks.front();
sharks.pop_front();
//check = true -> 인접한 아무 냄새가 없는 칸이 있는 경우, check = false -> 인접한 칸에 냄새가 모두 뿌려져 있는 경우
bool check = false;
for(int d=0; d<4; d++){
//현재 상어가 바라보고 있는 방향에 대한 우선순위에 따른 방향
int nd = now_shark.priority[now_shark.d][d];
int nx = now_shark.x + dx[nd];
int ny = now_shark.y + dy[nd];
//격자 밖으로 벗어난 경우, 무시한다
if(nx<0 || nx>=N || ny<0 || ny>=N) continue;
//아무 냄새가 없는 칸인 경우, 해당 상어의 위치와 방향을 바꿔주고 break
if(board[ny][nx][0] == 0){
check = true;
now_shark.x = nx;
now_shark.y = ny;
now_shark.d = nd;
break;
}
}
//아무 냄새가 없는 칸이 있는 경우,
if(check) {
//이동할 상어를 copy_sharks에 담고 다음 상어를 이동시킨다
copy_sharks.push_back(now_shark);
continue;
}
//자신의 냄새가 있는 칸으로 이동해야하는 경우,
for(int d=0; d<4; d++){
int nd = now_shark.priority[now_shark.d][d];
int nx = now_shark.x + dx[nd];
int ny = now_shark.y + dy[nd];
//격자 밖으로 벗어난 경우, 무시한다
if(nx<0 || nx>=N || ny<0 || ny>=N) continue;
//자신의 냄새가 있는 칸인 경우, 해당 상어의 위치와 방향을 바꿔주고 break
if(board[ny][nx][0] == now_shark.num){
now_shark.x = nx;
now_shark.y = ny;
now_shark.d = nd;
break;
}
}
//자신의 냄새가 있는 칸으로 이동할 상어를 copy_sharks에 담아준다
copy_sharks.push_back(now_shark);
}
//2. 이전에 뿌려진 냄새 타이머 가동
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
//냄새가 없는 칸인 경우, 넘어간다
if(board[y][x][0] == 0) continue;
//냄새가 있는 칸인 경우, 타이머 카운팅
board[y][x][1]--;
//타이머가 종료된 경우, 해당 칸에 냄새를 뿌렸던 상어 번호를 없애준다
if(board[y][x][1] == 0) board[y][x][0] = 0;
}
}
//3. 이동하기
while(!copy_sharks.empty()){
Shark now_shark = copy_sharks.front();
copy_sharks.pop_front();
//상어가 이동할 칸에 아무 냄새가 없거나, 자신의 냄새가 뿌려진 경우에만 상어를 이동시킨다
//번호가 적은 상어부터 이동하므로 이전에 자신의 번호보다 작은 번호의 상어가 있는 경우, 쫓겨나게 된다
if(board[now_shark.y][now_shark.x][0] == 0 || board[now_shark.y][now_shark.x][0] == now_shark.num){
//냄새 타이머 가동
board[now_shark.y][now_shark.x][0] = now_shark.num;
board[now_shark.y][now_shark.x][1] = k;
//sharks에 이동한 상어 추가
sharks.push_back(now_shark);
}
}
sec++;
}
}
int main(int argc, const char * argv[]) {
cin >> N >> M >> k;
//M마리의 상어를 sharks에 추가한다
for(int i=0; i<M; i++){
Shark shark;
shark.num = i+1;
sharks.push_back(shark);
}
for(int y=0; y<N; y++){
for(int x=0; x<N; x++){
cin >> board[y][x][0];
//해당 칸에 상어가 있는 경우
if(board[y][x][0] > 0){
//해당 상어의 위치를 설정하고 냄새 타이머를 k로 설정한다
sharks[board[y][x][0]-1].x = x;
sharks[board[y][x][0]-1].y = y;
board[y][x][1] = k;
}
}
}
//상어들의 초기 방향을 설정한다
for(int i=0; i<M; i++){
cin >> sharks[i].d;
}
//상어들의 방향 우선순위를 설정한다
for(int i=0; i<M; i++){
for(int d=1; d<=4; d++){
for(int j=0; j<4; j++){
cin >> sharks[i].priority[d][j];
}
}
}
move_sharks();
cout << sec << endl;
return 0;
}
//시간복잡도 = O(K*N^2), 공간복잡도 = O(N^2)이전 풀이
풀이 시간 2시간 15분
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int N, M, k;
int board[20][20] = {0, };
int sec = 0;
//1-위, 2-아래, 3-왼, 4-오
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, -1, 1, 0, 0};
struct Shark{
int x;
int y;
int num;
int dir;
int priority[5][4] = {0, };
};
Shark shark;
//현재 격자 안의 상어들을 담는 벡터
vector<Shark> sharks;
//상어 이동시킬 때 사용할 큐
queue<Shark> cp_sharks;
struct Smell{
int shark_num;
int timer = 0;
};
//smell[y][x] = 격자의 (x, y)에 뿌려진 냄새
Smell smell[20][20];
//남은 시간이 있는 냄새의 위치를 담는 벡터
vector<pair<int, int>> smell_locs;
//냄새 타이머를 카운팅할 때 쓸 벡터
vector<pair<int, int>> cp_smell_locs;
void move_sharks(){
//격자 안의 상어들을 이동시킨다
for(int i=0; i<sharks.size(); i++){
shark = sharks[i];
//인접한 칸 중 냄새가 없는 칸이 없으면 false, 있으면 true
bool ck = false;
//ck가 false일 때, 인접한 칸 중 자신의 냄새가 있는 칸의 방향 new_dir과 위치 new_x, new_y를 담는다
int new_x = -1;
int new_y = -1;
int new_dir = -1;
//우선순위에 따라 인접 칸 탐색
for(int j=0; j<4; j++){
int n_dir = sharks[i].priority[sharks[i].dir][j];
int nx = sharks[i].x + dx[n_dir];
int ny = sharks[i].y + dy[n_dir];
//격자 밖을 벗어나는 이동 방향은 무시한다
if(nx<0 || nx>=N || ny<0 || ny>=N) continue;
//냄새가 없는 칸이 있는 경우, cp_sharks에 담아주고 break
if(smell[ny][nx].timer == 0){
ck = true;
shark.x = nx;
shark.y = ny;
shark.dir = n_dir;
cp_sharks.push(shark);
break;
}
//자신의 냄새가 있는 칸인 경우, 그중 우선순위가 가장 큰 이동 방향으로 new_x, new_y, new_dir을 셋팅한다
else if(smell[ny][nx].shark_num == sharks[i].num){
if(new_x != -1) continue;
new_x = nx;
new_y = ny;
new_dir = n_dir;
}
}
//냄새가 없는 칸이 없는 경우, 자신의 냄새가 있는 칸으로 이동한다
if(!ck){
shark.x = new_x;
shark.y = new_y;
shark.dir = new_dir;
cp_sharks.push(shark);
}
}
//새로운 상어 상태를 받아오기 위해 sharks 벡터를 비워준다
sharks.clear();
//상어를 이동한 상태를 담아주기 위해 격자를 초기화한다
memset(board, 0, sizeof(board));
while(!cp_sharks.empty()){
shark = cp_sharks.front();
cp_sharks.pop();
//이미 빠른 번호의 상어가 이동할 칸에 있는 경우, 해당 상어는 격자 밖으로 쫓겨난다
if(board[shark.y][shark.x] != 0) continue;
//상어를 이동시킨다
board[shark.y][shark.x] = shark.num;
sharks.push_back(shark);
}
}
void count_timer(){
cp_smell_locs = smell_locs;
smell_locs.clear();
while(!cp_smell_locs.empty()){
int x = cp_smell_locs.back().first;
int y = cp_smell_locs.back().second;
cp_smell_locs.pop_back();
//냄새 타이머를 가동시킨다
smell[y][x].timer--;
//냄새 타이머가 0이 된 경우, 더 이상 가동시키지 않는다
if(smell[y][x].timer == 0) continue;
//냄새 타이머가 0보다 큰 경우, 타이머 가동을 위해 smell_locs에 위치를 담는다
smell_locs.push_back({x, y});
}
}
void spread_smell(){
for(int i=0; i<sharks.size(); i++){
//이동한 상어의 위치에 냄새를 뿌린다
smell[sharks[i].y][sharks[i].x].shark_num = sharks[i].num;
//냄새가 없는 칸으로 이동한 경우, 타이머 가동을 위해 해당 위치를 smell_locs에 담는다
if(smell[sharks[i].y][sharks[i].x].timer == 0){
smell_locs.push_back({sharks[i].x, sharks[i].y});
}
smell[sharks[i].y][sharks[i].x].timer = k;
}
}
void play(){
while(true){
sec++;
//1000초까지 while문을 실행한다
if(sec > 1000){
sec = -1;
return;
}
//1. 상어 움직이기 -> O(M) = O(N^2)
move_sharks();
//2. 냄새 타이머 가동(1초 빼기) -> O(M) = O(N^2)
count_timer();
//3. 움직인 상어 위치에 냄새 뿌리기 -> O(M) = O(N^2)
spread_smell();
//4. 격자 안 상어 카운팅 -> 1번 상어만 남으면 while문을 빠져나온다.
if(sharks.size() == 1) break;
}
}
int main(int argc, const char * argv[]) {
cin >> N >> M >> k;
//M 마리의 상어를 sharks에 담아준다
for(int i=1; i<=M; i++){
shark.num = i;
sharks.push_back(shark);
}
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
cin >> board[i][j];
//격자 칸에 상어가 있는 경우
if(board[i][j] != 0){
//sharks 벡터에 담긴 해당 상어의 위치를 셋팅한다
sharks[board[i][j]-1].x = j;
sharks[board[i][j]-1].y = i;
//상어가 처음 위치한 곳에 냄새를 뿌려준다
smell[i][j].timer = k;
smell[i][j].shark_num = board[i][j];
smell_locs.push_back({j, i});
}
}
}
//각 상어의 방향을 입력에서 받아온다
for(int i=0; i<M; i++){
cin >> sharks[i].dir;
}
//각 상어의 방향 우선순위를 입력에서 받아온다
for(int i=0; i<M; i++){
for(int j=1; j<=4; j++){
for(int k=0; k<4; k++){
cin >> sharks[i].priority[j][k];
}
}
}
play();
cout << sec << endl;
return 0;
}
//시간복잡도 = O(K*N^2) -> O(n^3), 공간복잡도 = O(N^2)
728x90
반응형
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 16472 고냥이 Python3 (0) | 2021.10.04 |
|---|---|
| 백준 3649 로봇 프로젝트 Python3 (0) | 2021.10.04 |
| 백준 17822 원판 돌리기 C++ (0) | 2021.10.03 |
| 백준 3686 성냥개비 Python 3 (0) | 2021.10.02 |
| 백준 20057 마법사 상어와 토네이도 C++ (0) | 2021.09.16 |