알고리즘/백준 문제 풀이
[BOJ] 19237. 어른 상어
바켱서
2020. 7. 31. 00:38
https://www.acmicpc.net/problem/19237
접근 방법
청소년 상어가 자라서 어른상어가 되었다...
그래도 청소년 상어보다는 쉽게 느껴졌다.
그냥 구현을 쭉 해주면 되었다.
먼저 현재 있는 위치의 상어들이 냄새를 뿌린 코드이다.
static void saveSmell(){ for(int i=0; i<N; i++){ for(int k=0; k<N; k++){ if(map[i][k].shark_num != 0){ map[i][k].smell_time = K; map[i][k].smell_master = map[i][k].shark_num; } } } }다음 상어들이 움직인다.
static Location[][] movingShark(){ Location[][] cloneMap = new Location[N][N]; for(int i=0; i<N; i++){ for(int k=0; k<N; k++){ cloneMap[i][k] = new Location(map[i][k]); } } for(int i=0; i<N; i++){ for(int k=0; k<N; k++){ int nowShark = map[i][k].shark_num; if(nowShark != 0){ // 현재 상어가 바라 보고 있는 방향. int shark_direction = currentSharkDirection[map[i][k].shark_num]; // find next location int flag = 0; for(int z = 0; z<4; z++){ int nx = i + dx[z]; int ny = k + dy[z]; if(checkOutIndex(nx,ny)){ if(map[nx][ny].smell_time == 0){ flag ++; } } } // 냄새가 여러 방면 으로 다 존재 한다. if(flag == 0){ loop1:for(int z=0; z<4; z++){ int nx = i + dx[sharkDir[nowShark][shark_direction][z]]; int ny = k + dy[sharkDir[nowShark][shark_direction][z]]; if(checkOutIndex(nx,ny)){ if(map[nx][ny].smell_master != map[i][k].shark_num ) continue loop1; cloneMap[i][k].shark_num = 0; cloneMap[nx][ny].shark_num = nowShark; currentSharkDirection[nowShark] = sharkDir[nowShark][shark_direction][z]; break loop1; } } }else{ loop:for(int z=0; z<4; z++){ int nx = i + dx[sharkDir[nowShark][shark_direction][z]]; int ny = k + dy[sharkDir[nowShark][shark_direction][z]]; if(checkOutIndex(nx,ny)){ if(map[nx][ny].smell_time != 0 ) continue loop; // 갈 장소에 다른 상어가 존재 if(cloneMap[nx][ny].shark_num != 0 ){ if( map[i][k].shark_num < cloneMap[nx][ny].shark_num ){ cloneMap[nx][ny].shark_num = map[i][k].shark_num; } cloneMap[i][k].shark_num = 0; } // 갈 장소가 일단은 비어 있다. else{ int temp = cloneMap[i][k].shark_num; cloneMap[i][k].shark_num = 0; cloneMap[nx][ny].shark_num = temp; } currentSharkDirection[nowShark] = sharkDir[nowShark][shark_direction][z]; break loop; } } } } } }모든 냄새의 시간을 -1 을 해준다.
static void timeGoing(){ // time going for(int i=0; i<N; i++) { for (int k = 0; k < N; k++) { int nowSmell = map[i][k].smell_time; if (nowSmell != 0 ) { map[i][k].smell_time--; if (map[i][k].smell_time == 0) { map[i][k].smell_master = 0; } } } } }1만 남아있는지 아니면 1000초가 초과가 되었는지 확인하자.
static boolean checkEnd(){ if(time == 1001) return true; for(int i=0; i<N; i++){ for(int k=0; k<N; k++){ if(map[i][k].shark_num != 0 && map[i][k].shark_num != 1){ return false; } } } return true; }
주의 사항
- 상어가 움직일 때 우선순위는 냄새가 없는 곳이 1순위다.
- 문제를 잘 보면 상어는 자신의 냄새가 있는 곳에 갈 수 있는데, 여기서도 우선순위는 적용되어야한다.
Need Know
- 구현
전체 코드 ( Java )
import java.io.*;
import java.util.*;
class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N; // 격자 크기
static int M; // 상어 갯수
static int K; // 냄새 효과 시간
static Location[][] map; // 가지고 있는 정보는 각 배열의 상어의 번호, 냄새, 냄새뿌린 상어
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int[][][] sharkDir; // 각 상어들의 찾는 방향의 우선순위
static int[] currentSharkDirection; // 각 상어들의 현재 방향
static int time = 0; // 시간 _ 1000이 넘어가면 -1 출력
public static void main(String[] args) throws IOException {
set();
solve();
bw.flush();
bw.close();
br.close();
}
static void set() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new Location[N][N];
sharkDir = new int[M+1][4][4];
currentSharkDirection = new int[M+1];
for(int i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
for(int k=0; k<N; k++){
map[i][k] = new Location(Integer.parseInt(st.nextToken()),0,0);
}
}
// 상어들의 첫 방향
st = new StringTokenizer(br.readLine());
for(int i=1; i<M+1; i++){
currentSharkDirection[i] = (Integer.parseInt(st.nextToken())-1);
}
for(int i=1; i<M+1; i++){
// i - 몇번 째 상어
for(int k=0; k<4; k++){
// k에 따라 위 아래 왼쪽 오른쪽
st = new StringTokenizer(br.readLine());
for(int j=0; j<4; j++){
// j 에 따라 우선 순위
sharkDir[i][k][j] = (Integer.parseInt(st.nextToken())-1);
}
}
}
}
// 이동 할 때 순위.
// 1. 인접한 칸 중 아무 냄새가 없는 칸의 방향
// 2. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향
// 3. 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위
static void solve() throws IOException {
saveSmell();
while(true){
saveSmell();
// printTime();
// System.out.println();
map = movingShark();
// printMap();
// System.out.println();
timeGoing();
time++;
if(checkEnd()) break;
}
bw.write((time!=1001 ? time : -1) + "");
}
static void printTime(){
for(int i=0; i<N; i++){
for(int k=0; k<N; k++){
System.out.print(map[i][k].smell_time +" ");
}
System.out.println();
}
}
static void printMap(){
for(int i=0; i<N; i++){
for(int k=0; k<N; k++){
System.out.print(map[i][k].shark_num +" ");
}
System.out.println();
}
}
static void saveSmell(){
for(int i=0; i<N; i++){
for(int k=0; k<N; k++){
if(map[i][k].shark_num != 0){
map[i][k].smell_time = K;
map[i][k].smell_master = map[i][k].shark_num;
}
}
}
}
static Location[][] movingShark(){
Location[][] cloneMap = new Location[N][N];
for(int i=0; i<N; i++){
for(int k=0; k<N; k++){
cloneMap[i][k] = new Location(map[i][k]);
}
}
for(int i=0; i<N; i++){
for(int k=0; k<N; k++){
int nowShark = map[i][k].shark_num;
if(nowShark != 0){
// 현재 상어가 바라 보고 있는 방향.
int shark_direction = currentSharkDirection[map[i][k].shark_num];
// find next location
int flag = 0;
for(int z = 0; z<4; z++){
int nx = i + dx[z];
int ny = k + dy[z];
if(checkOutIndex(nx,ny)){
if(map[nx][ny].smell_time == 0){
flag ++;
}
}
}
// 냄새가 여러 방면 으로 다 존재 한다.
if(flag == 0){
loop1:for(int z=0; z<4; z++){
int nx = i + dx[sharkDir[nowShark][shark_direction][z]];
int ny = k + dy[sharkDir[nowShark][shark_direction][z]];
if(checkOutIndex(nx,ny)){
if(map[nx][ny].smell_master != map[i][k].shark_num ) continue loop1;
cloneMap[i][k].shark_num = 0;
cloneMap[nx][ny].shark_num = nowShark;
currentSharkDirection[nowShark] = sharkDir[nowShark][shark_direction][z];
break loop1;
}
}
}else{
loop:for(int z=0; z<4; z++){
int nx = i + dx[sharkDir[nowShark][shark_direction][z]];
int ny = k + dy[sharkDir[nowShark][shark_direction][z]];
if(checkOutIndex(nx,ny)){
if(map[nx][ny].smell_time != 0 ) continue loop;
// 갈 장소에 다른 상어가 존재
if(cloneMap[nx][ny].shark_num != 0 ){
if( map[i][k].shark_num < cloneMap[nx][ny].shark_num ){
cloneMap[nx][ny].shark_num = map[i][k].shark_num;
}
cloneMap[i][k].shark_num = 0;
}
// 갈 장소가 일단은 비어 있다.
else{
int temp = cloneMap[i][k].shark_num;
cloneMap[i][k].shark_num = 0;
cloneMap[nx][ny].shark_num = temp;
}
currentSharkDirection[nowShark] = sharkDir[nowShark][shark_direction][z];
break loop;
}
}
}
}
}
}
return cloneMap;
}
static boolean checkOutIndex(int nx, int ny){
if( nx >= N || ny >= N || nx < 0 || ny < 0 ) return false;
return true;
}
static void timeGoing(){
// time going
for(int i=0; i<N; i++) {
for (int k = 0; k < N; k++) {
int nowSmell = map[i][k].smell_time;
if (nowSmell != 0 ) {
map[i][k].smell_time--;
if (map[i][k].smell_time == 0) {
map[i][k].smell_master = 0;
}
}
}
}
}
static boolean checkEnd(){
if(time == 1001) return true;
for(int i=0; i<N; i++){
for(int k=0; k<N; k++){
if(map[i][k].shark_num != 0 && map[i][k].shark_num != 1){
return false;
}
}
}
return true;
}
}
class Location{
int shark_num, smell_time, smell_master;
public Location(int shark_num, int smell_time, int smell_master) {
this.shark_num = shark_num;
this.smell_time = smell_time;
this.smell_master = smell_master;
}
public Location(Location location) {
this.shark_num = location.shark_num;
this.smell_master = location.smell_master;
this.smell_time = location.smell_time;
}
}