어른 상어 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	756	343	233	42.831%

문제

청소년상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.

각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

<그림 1>

우선 순위
상어 1	상어 2	상어 3	상어 4
↑	↓ ← ↑ →	↑	↓ → ← ↑	↑	→ ← ↓ ↑	↑	← → ↑ ↓
↓	→ ↑ ↓ ←	↓	↓ ↑ ← →	↓	↑ → ← ↓	↓	← ↓ → ↑
←	← → ↓ ↑	←	← → ↑ ↓	←	↑ ← ↓ →	←	↑ → ↓ ←
→	→ ← ↑ ↓	→	→ ↑ ↓ ←	→	← ↓ ↑ →	→	↑ → ↓ ←

<표 1>

<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.

<그림 2>

<그림 3>

<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.

<그림 4>

<그림 5>

<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.

이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.

입력

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)

그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.

맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

출력

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

예제 입력 1 복사

예제 출력 1 복사


xxxxxxxxxx
14

문제에 나온 그림과 같다.

예제 입력 2 복사

예제 출력 2 복사


xxxxxxxxxx
26

예제 입력 3 복사

예제 출력 3 복사


xxxxxxxxxx
-1

예제 입력 4 복사

풀이

삼성 SW 기출 문제

시간처리 해주는것에서.... 좀 애를 먹긴 했는데 혼자 힘으로 풀었다.

선언한 클래스들


class Shark{
    int x,y,dir;
    boolean flag;
    Shark(int x, int y, int dir,boolean flag){
        this.x=x;
        this.y=y;
        this.dir=dir;
        this.flag=flag;
    }
}

가장 먼저 Shark 클래스다.

이건 1번부터 n번까지의 상어의 정보를 저장해주는 배열에 쓰려고 만들었다.

x,y는 현재 상어의 위치,

dir 현재 방향

flag는 살아있는지, 죽어있는지 가늠하기 위해 사용했다.


class Node{
    int num,time;
    Node(int num, int time){
        this.num = num;
        this.time=time;
    }
}

그 다음 map에서 표현할 Node 클래스를 만들었다.

내가 map에서 표현하려고 의도했던건

map[0] [0] 에서 접근할수 있는 정보는 상어냄새의 시간+어떤 상어의 냄새인지를 얻기 위해서 설정했다.

즉 맵에는 냄새가 사라지기 전까지의 남은 시간과 어떤 상어의 냄새인지 표시를 했다.


class Tmp{
    int x,y;
    Tmp(int x, int y){
        this.x=x;
        this.y=y;
    }
}

이건 상어의 이동에 따른 시간계산에서 쓰려고 만들었다.

문제에서 구현해야 하는건, 1번부터 n번까지의 상어가 "동시에" 이동을 하고 같은 칸에 도착 했을 경우

번호가 낮은 상어가 번호 높은 상어를 잡아 먹는 로직이다.

그래서 상어를 map에서 이동시켜주지 않고 우선 Tmp 라는 배열+리스트에 담아두고

번호가 낮은 상어가 먼저 방문을 했다면 번호가 높은 상어는 map에서 냄새와 어떤상어인지를

적어주지 않고 죽였다는 표시를 했다.

전체코드


xxxxxxxxxx
import java.io.*;
import java.util.*;
public class Main {
    static int n,m,k;
    static Node map[][];
    static int dx[] = {0,-1,1,0,0};
    static int dy[] = {0,0,0,-1,1};
    static Shark[] shark;
    static ArrayList<Integer>list[][];
    static ArrayList<Tmp>tmp_list[];
    static boolean visited[][];
    
    static int ans=0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String [] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]); //n * n 맵의 크기
        m = Integer.parseInt(t[1]);// 상어의 개수
        k = Integer.parseInt(t[2]); // 시간
        visited = new boolean[n+1][n+1];
        map = new Node[n][n];
        shark = new Shark[m+1];
        list = new ArrayList[m+1][5];
    
    
        for(int i=0; i<n; i++) {
            String[] map_input = br.readLine().split(" ");
            for(int j=0; j<n; j++) {
                int s_num = Integer.parseInt(map_input[j]);
                if(s_num==0) {
                    map[i][j] = new Node(0,0); 
                }
                else{
                    map[i][j] = new Node(s_num,k);
                    shark[s_num] = new Shark(i,j,0,true);
                }
            }
        }
        
        String[] dir_input = br.readLine().split(" ");
        for(int i=0; i<dir_input.length; i++) {
            shark[i+1].dir = Integer.parseInt(dir_input[i]);
        }
        for(int i=0; i<list.length; i++) {
            for(int j=1; j<5; j++) {
                list[i][j] = new ArrayList<>();
            }
        }
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=4; j++) {
                String [] tt = br.readLine().split(" ");
                for(int k=0; k<4; k++) {
                    list[i][j].add(Integer.parseInt(tt[k]));
                }
            }
        }
        
        
        solve();
        
    }
    public static void solve() {
        while(true) {
            visited = new boolean[n+1][n+1];
            tmp_list = new ArrayList[m+1];
            for(int i=1; i<=m; i++) {
                tmp_list[i] = new ArrayList<>();
            }
            if(ans>1000) {
                System.out.println(-1);
                break;
            }
            if(game_end()) {
                System.out.println(ans);
                break;
            }
            
            
            // 1. 상어가 움직인다.
            for(int i=1; i<=m; i++) {
                if(shark[i].flag==false) {  // 죽어있는 상어는 무시함
                    continue;
                }
                int x = shark[i].x;
                int y = shark[i].y;
                // 1-1 인접한 방향중 냄새가 없는칸이 있는지 확인하기
                if(isPossible(i)) {
                    // 1-2 우선순위에 따라 방향 결정하기
                    int change_dir = get_dir(i);
                    // 1-3 상어 위치 바꿔주기
                    int nx = x+dx[change_dir];
                    int ny = y+dy[change_dir];
                    shark[i].x = nx;
                    shark[i].y = ny;
                    shark[i].dir =change_dir;
                    // 1-4 해당칸에 냄새뿌릴 정보 저장
                    tmp_list[i].add(new Tmp(nx,ny));
                }
                else {  //2. 인접방향중 냄새없는 칸이 없다면 인접한 칸으로 돌아가기
                    int back_dir = rollback_dir(i);
                    // 2-1 상어위치 바꿔주기
                    int nx = x+dx[back_dir];
                    int ny = y+dy[back_dir];
                    shark[i].x = nx;
                    shark[i].y = ny;
                    shark[i].dir = back_dir;
                    map[nx][ny].num = i;
                    map[nx][ny].time=k;
                    visited[nx][ny] = true;
                }
            }
            
            for(int i=1; i<=m; i++) {
                if(tmp_list[i].size()==0) {
                    continue;
                }
                int tmp_x = tmp_list[i].get(0).x;
                int tmp_y = tmp_list[i].get(0).y;
                if(visited[tmp_x][tmp_y]) {
                    shark[i].flag = false;
                }
                else {
                    visited[tmp_x][tmp_y] = true;
                    map[tmp_x][tmp_y].num =i;
                    map[tmp_x][tmp_y].time =k;
                }
            }
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    if(map[i][j].num!=0 && !visited[i][j]) {
                        map[i][j].time--;
                        if(map[i][j].time==0) {
                            map[i][j].num=0;
                        }
                    }
                }
            }
            ans++;
        }
        
    }
    public static boolean game_end() {
        for(int i=2; i<=m; i++) {
            if(shark[i].flag==true) {
                return false;
            }
        }
        return true;
    }
    public static int rollback_dir(int s_num) {
        int x = shark[s_num].x;
        int y = shark[s_num].y;
        int dir = shark[s_num].dir;
        
        for(int i=0; i<4; i++) {
            int tmp_dir = list[s_num][dir].get(i);
            int nx = x+dx[tmp_dir];
            int ny = y+dy[tmp_dir];
            if(isRange(nx,ny) && map[nx][ny].num==s_num) {
                return tmp_dir;
            }
        }
        return 1000;
    }
    public static int get_dir(int s_num) {
        int x = shark[s_num].x;
        int y = shark[s_num].y;
        int dir =shark[s_num].dir;
        for(int i=0; i<4; i++) {
            int tmp_dir = list[s_num][dir].get(i);
            int nx = x+dx[tmp_dir];
            int ny = y+dy[tmp_dir];
            if(isRange(nx,ny) && map[nx][ny].num==0) {
                return tmp_dir;
            }
        }
        return 10000;
    }
    public static boolean isPossible(int s_num) {
        // 1. 일단 맵의 범위안에서만 탐색가능
        int x = shark[s_num].x;
        int y = shark[s_num].y;
        for(int i=1; i<=4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(isRange(nx,ny)) {
                if(map[nx][ny].num==0) {
                    return true;
                }
            }
        }
        return false;
    }
    public static boolean isRange(int x ,int y) {
        if(x>=0 && y>=0 && x<n && y<n) {
            return true;
        }
        return false;
    }
}
class Shark{
    int x,y,dir;
    boolean flag;
    Shark(int x, int y, int dir,boolean flag){
        this.x=x;
        this.y=y;
        this.dir=dir;
        this.flag=flag;
    }
}
class Node{
    int num,time;
    Node(int num, int time){
        this.num = num;
        this.time=time;
    }
}
class Tmp{
    int x,y;
    Tmp(int x, int y){
        this.x=x;
        this.y=y;
    }
}

저작자표시

'알고리즘' 카테고리의 다른 글

[백준 1941] 소문난 칠공주-JAVA//le_effort (0)	2020.08.11
[2019 카카오 개발자 겨울 인턴십] 불량 사용자-JAVA//le_effort (0)	2020.08.09
[2019 카카오 개발자 겨울 인턴십] 튜플-JAVA//le_effort (0)	2020.07.31
[2019 카카오 개발자 겨울 인턴십] 크레인 인형뽑기 게임-JAVA//le_effort (0)	2020.07.31
[백준 19236] 청소년 상어 -JAVA //le_effort (0)	2020.07.31

일	월	화	수	목	금	토
						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

공부 기록용 블로그

[백준 19237] 어른상어 -JAVA //le_effort

어른 상어 성공

문제

입력

출력

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

예제 입력 3 복사

예제 출력 3 복사

예제 입력 4 복사

풀이

선언한 클래스들

전체코드

'알고리즘' 카테고리의 다른 글

티스토리툴바

어른 상어 성공

문제

입력

출력

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

예제 입력 3 복사

예제 출력 3 복사

예제 입력 4 복사

풀이

선언한 클래스들

전체코드

'알고리즘' 카테고리의 다른 글

검색

티스토리툴바