글 읽기 - 아기상어 예제4번과 시간초과 문제 도와주세요 ㅜㅜ

kkkkkkya 5년 전 1

일단 제 코드는 첨부와 같고,

4번 예제의 결과 값이 왜 60인지 이해되지 않아 문의드립니다 ㅠㅠ

저는 문제에 주어진 요구사항을 고려해 물고기를 먹는 순간들을 따라가 보았습니다.

- 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.

- 1초 마다 좌/우/상/하 1칸 씩 이동

- 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.

- 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.

- 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

- 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.

> 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최소값이다.

> 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

> 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다.

즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

그 결과,

(3, 1) 2초, 크기 : 2, 먹이 : 1

(4, 2) 4초, 크기 : 3, 먹이 : 0

(3, 2) 5초, 크기 : 3, 먹이 : 1

(2, 1) 7초, 크기 : 3, 먹이 : 2

(1, 2) 9초, 크기 : 4, 먹이 : 0

(0, 2) 10초, 크기 : 4, 먹이 : 1

(0, 3) 11초, 크기 : 4, 먹이 : 2

(0, 4) 12초, 크기 : 4, 먹이 : 3

(1, 3) 14초, 크기 : 5, 먹이 : 0

(1, 4) 15초, 크기 : 5, 먹이 : 1

(0, 5) 17초, 크기 : 5, 먹이 : 2

(0, 1) 21초, 크기 : 5, 먹이 : 3

(1, 1) 22초, 크기 : 5, 먹이 : 4

(1, 0) 23초, 크기 : 6, 먹이 : 0

(0, 0) 24초, 크기 : 6, 먹이 : 1

(2, 0) 26초, 크기 : 6, 먹이 : 2

(3, 0) 27초, 크기 : 6, 먹이 : 3

(4, 0) 28초, 크기 : 6, 먹이 : 4

(4, 1) 29초, 크기 : 6, 먹이 : 5

(3, 3) 32초, 크기 : 7, 먹이 : 0

(2, 3) 33초, 크기 : 7, 먹이 : 1

(2, 4) 34초, 크기 : 7, 먹이 : 2

(2, 5) 35초, 크기 : 7, 먹이 : 3

(1, 5) 36초, 크기 : 7, 먹이 : 4

(3, 5) 38초, 크기 : 7, 먹이 : 5

(3, 4) 39초, 크기 : 7, 먹이 : 6

(4, 4) 40초, 크기 : 8, 먹이 : 0

(4, 3) 41초, 크기 : 8, 먹이 : 1

(5, 3) 42초, 크기 : 8, 먹이 : 2

(5, 2) 43초, 크기 : 8, 먹이 : 3

(5, 1) 44초, 크기 : 8, 먹이 : 4

(5, 0) 45초, 크기 : 8, 먹이 : 5

(5, 4) 49초, 크기 : 8, 먹이 : 6

(5, 5) 50초, 크기 : 8, 먹이 : 7

(4, 5) 51초, 크기 : 9, 먹이 : 0

이런 순서로 움직이고 물고기를 먹어, 51초가 답이 될 것 같은데 ㅠㅠ

제 생각과 따라간 순서가 어디가 잘못됐을까요 ? ㅠㅠ

더불어, 코드 채점하면 시간 초과가 납니다.

어떤 부분이 문제일 지 아낌없는 !! 조언 주시면 감사하겠습니다 !! ♥

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	// map : N * N
	// 물고기 먹는 기준
	/*
	 * 1. 아기상어 처음 크기 2, 1초에 상하좌우 한 칸
	 * 2. 자신 크기보다 큰 물고기가 있는 칸 지날 수 X
	 * 3. 자신 크기보다 작은 물고기는 eat
	 * 4. 결정하는 기준
	 * - 공간에 먹을 수 있는 물고기가 없으면 finish
	 * - 먹을 수 있는 물고기가 1마리라면, 그 물고기 eat
	 * - 1마리보다 많으면 거리가 가까운 물고기 eat
	 *    * 거리 : 물고기가 있는 칸까지 갈 때 지나가야하는 칸의 수
	 *    * 거리가 같다면, 가장 위, 그 다음은 가장 왼쪽
	 */
	
	public static class pos{
		int x;
		int y;
		int time;
		public pos(int x, int y, int time ) {
			super();
			this.x = x;
			this.y = y;
			this.time = time;
		}
		
	}
	
	static int map[][];
	static boolean v[][]; // visit flag 배열
	static int N; // 공간의 크기
	static int[] dx = {0, 0, -1, +1};
	static int[] dy = {+1, -1, 0, 0};
	static int eatCnt; // 현재 크기에서 먹은 고기 수
	static int mySize; // 현재 아기상어 크기
	static Queue<pos> q;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map = new int[N][N];
		v = new boolean[N][N];
		pos myPos = null;
		q = new LinkedList<pos>();
		mySize = 2;
		eatCnt = 0;
		boolean flag = true;
		
		for(int i=0; i<N; i++){
			Arrays.fill(v[i], false);
			for(int j=0; j<N; j++){
				map[i][j] = sc.nextInt();
				if(map[i][j] == 9){
					myPos = new pos(i, j, 0);
				}
			}
		}
		
		// 입력 완료
		v[myPos.x][myPos.y] = true;
		q.offer(myPos);
		map[myPos.x][myPos.y] = 0;
		
		if(!checkPossible()){
			System.out.println(0);
			return;
		}
		
		boolean canIeat;
		
		while(flag){
		canIeat = false;
		
		while(!q.isEmpty()){
			pos now = q.poll();
			
			for(int i=0; i<4; i++){
				// 이동 가능한 칸 탐색
				pos next = new pos(now.x + dx[i], now.y + dy[i], now.time + 1);
				
				if(next.x >= 0 && next.x < N && next.y >= 0 && next.y < N) {
					if(!v[next.x][next.y] && map[next.x][next.y] <= mySize){
						
						if(map[next.x][next.y] > 0 && map[next.x][next.y] < mySize){
							canIeat = true;
                            // canIeat이 true이면 탐색을 멈춤
						}
						
						v[next.x][next.y] = true;
						q.offer(next);
					}
				}
			}
			
			if(canIeat){
				break;
			}
		}
		
		if(canIeat){
			pos sel = new pos(N-1, N-1, Integer.MAX_VALUE);
				
            while(!q.isEmpty()){
					pos temp = q.poll();
					// 먹을 물고기 선정 
                    // 1. 물고기가 있는 칸 이고
					if(map[temp.x][temp.y] > 0 && map[temp.x][temp.y] < mySize){
						// 2. 최소 시간 이며
						if(temp.time < sel.time ){
							sel = temp;
						} else if (temp.time == sel.time){
							// 3. 최소 시간이 동일하다면
							if(temp.x < sel.x){
                                // 위쪽
								sel = temp;
							} else if (temp.x == sel.x){
								// 위쪽에 여러개라면
                                if(temp.y < sel.y){
                                    // 왼쪽
									sel = temp;
								}
							}
							
						}
					}
					
				}
				
				// 먹기
				map[sel.x][sel.y] = 0;
				eatCnt ++;
				
				if(eatCnt == mySize){
					mySize ++;
					eatCnt = 0;
				}
				
				
				if(checkPossible()){
					flag = true;
					
					for(int i=0; i<N; i++){
						Arrays.fill(v[i], false);
					}
                    // 새로 탐색해야하기에 visit flag 배열 초기화
					
					q.clear();

					v[sel.x][sel.y] = true;
					q.offer(sel);
				
				} else {
                    // 먹을 수 있는 물고기가 없는 return point
					flag = false;
					System.out.println(sel.time);
					return;
				}
			
			}
		}
		
	}
	
	public static boolean checkPossible(){
        // 먹을 수 있는 물고기가 있는지 확인하는 함수
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				if(map[i][j] < mySize && map[i][j]>0){
					return true;
				}
			}
		}
		
		return false;
	}

}

kau_algoitsm 5년 전 1

169번줄에 checkPossible 함수로는 루프가 끝나야 하는 지를 정확하게 판단할 수 없습니다

상어보다 작은 물고기가 있다고 해서 꼭 먹을 수 있는 것은 아닙니다

9 3

3 1

위와 같은 상황에선 먹을 수 있는 물고기는 있지만 먹을 수 없습니다

3, 1 : 2
4, 2 : 4
3, 2 : 5
1, 2 : 7
0, 3 : 9
0, 2 : 10
0, 4 : 12
1, 3 : 14
1, 1 : 16
0, 1 : 17
1, 0 : 19
2, 0 : 20
2, 1 : 21
3, 0 : 23
4, 0 : 24
4, 1 : 25
3, 3 : 28
2, 3 : 29
1, 4 : 31
1, 5 : 32
0, 5 : 33
2, 5 : 35
2, 4 : 36
3, 4 : 37
3, 5 : 38
4, 5 : 39
4, 4 : 40
4, 3 : 41
5, 3 : 42
5, 2 : 43
5, 1 : 44
5, 0 : 45
5, 4 : 49
5, 5 : 50
0, 0 : 60

도움이 되었으면 좋겠습니당

kkkkkkya 5년 전 0

아아 저는 말씀해주신 상황의 경우, 84 ~ 95 로직에서 걸러져서 멈출꺼라 생각했나봅니다...! PC로 다시 확인해보고 참고하도록 하겠습니다 :) 감사합니다 !!!!

kkkkkkya 5년 전 0

으어 완전 감사드립니다 ㅜㅜ 혼자 콕 박혀있던걸 도와주셔서 ㅜㅜ !!! 감사합니다 ! 좋은 하루되세요 !!!!!

djm03178 5년 전 3

전체 과정을 올려드립니다.

79번째 줄의 루프를 보면, 어떤 칸을 하나 빼고, 그 주변 4칸에서 먹을 수 있는 물고기가 하나라도 있다면 바로 루프를 탈출하고 있습니다. 하지만 이렇게 하면 동시간에 도달할 수 있는 모든 칸을 검사하지 못합니다. 예를 들어 어떤 칸에서 시작해서 상하좌우 4칸으로 모두 움직일 수 있다면, 큐에 4개의 원소가 한 번에 들어가게 됩니다. 그 후 원소를 하나 꺼내게 되면 여전히 세 개의 원소는 큐에 남아있는 상태인데, 꺼낸 칸의 4방향 주변에 먹을 수 있는 물고기가 있다면 아직 큐에 남아있는 3개의 칸의 주변에 먹을 수 있는 물고기가 있는지 여부는 확인하지 않고 바로 루프를 탈출하게 됩니다.

정답과의 차이를 보면 처음으로 달라지는 곳이 7초에서 (1, 2)가 아니라 (2, 1)로 가고 있는데, (1, 2)가 더 위쪽에 있으므로 이쪽에 가야 하지만, 그 전에 있었던 (3, 2)에서 (2, 2)보다 (3, 1)을 먼저 탐색해 들어갔기 때문에, (3, 1)의 주변에 있던 (2, 1)만 보고 먹을 수 있는 물고기가 있다고 판단하고 루프를 바로 빠져나가는 발마에 (2, 2)의 주변에 뭐가 있는지는 확인조차 하지 않은 것입니다.

[2]: (3, 1), size = 2
4 3 2 3 4
3 2 3 4 5
2 0 5 6 6
0 2 3 4 5
2 1 6 5 4
6 6 6 6 6

[4]: (4, 2), size = 3
4 3 2 3 4
3 2 3 4 5
2 0 5 6 6
0 2 3 4 5
2 0 6 5 4
6 6 6 6 6

[5]: (3, 2), size = 3
4 3 2 3 4
3 2 3 4 5
2 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[7]: (1, 2), size = 3
4 3 2 3 4
3 0 3 4 5
2 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[9]: (0, 3), size = 4
4 3 0 3 4
3 0 3 4 5
2 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[10]: (0, 2), size = 4
4 0 0 3 4
3 0 3 4 5
2 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[12]: (0, 4), size = 4
4 0 0 0 4
3 0 3 4 5
2 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[14]: (1, 3), size = 4
4 0 0 0 4
3 0 0 4 5
2 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[16]: (1, 1), size = 5
4 0 0 0 4
0 0 0 4 5
2 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[17]: (0, 1), size = 5
0 0 0 0 4
0 0 0 4 5
2 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[19]: (1, 0), size = 5
0 0 0 0 4
0 0 0 4 5
2 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[20]: (2, 0), size = 5
0 0 0 0 4
0 0 0 4 5
2 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[21]: (2, 1), size = 5
0 0 0 0 4
0 0 0 4 5
0 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[23]: (3, 0), size = 6
0 0 0 0 4
0 0 0 4 5
0 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[24]: (4, 0), size = 6
0 0 0 0 4
0 0 0 4 5
0 0 5 6 6
0 0 3 4 5
2 0 6 5 4
6 6 6 6 6

[25]: (4, 1), size = 6
0 0 0 0 4
0 0 0 4 5
0 0 5 6 6
0 0 3 4 5
0 0 6 5 4
6 6 6 6 6

[28]: (3, 3), size = 6
0 0 0 0 4
0 0 0 4 5
0 0 5 6 6
0 0 0 4 5
0 0 6 5 4
6 6 6 6 6

[29]: (2, 3), size = 6
0 0 0 0 4
0 0 0 4 5
0 0 0 6 6
0 0 0 4 5
0 0 6 5 4
6 6 6 6 6

[31]: (1, 4), size = 6
0 0 0 0 4
0 0 0 0 5
0 0 0 6 6
0 0 0 4 5
0 0 6 5 4
6 6 6 6 6

[32]: (1, 5), size = 7
0 0 0 0 4
0 0 0 0 0
0 0 0 6 6
0 0 0 4 5
0 0 6 5 4
6 6 6 6 6

[33]: (0, 5), size = 7
0 0 0 0 0
0 0 0 0 0
0 0 0 6 6
0 0 0 4 5
0 0 6 5 4
6 6 6 6 6

[35]: (2, 5), size = 7
0 0 0 0 0
0 0 0 0 0
0 0 0 6 0
0 0 0 4 5
0 0 6 5 4
6 6 6 6 6

[36]: (2, 4), size = 7
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 4 5
0 0 6 5 4
6 6 6 6 6

[37]: (3, 4), size = 7
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 5
0 0 6 5 4
6 6 6 6 6

[38]: (3, 5), size = 7
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 6 5 4
6 6 6 6 6

[39]: (4, 5), size = 7
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 6 5 0
6 6 6 6 6

[40]: (4, 4), size = 8
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 6 0 0
6 6 6 6 6

[41]: (4, 3), size = 8
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
6 6 6 6 6

[42]: (5, 3), size = 8
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
6 6 0 6 6

[43]: (5, 2), size = 8
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
6 0 0 6 6

[44]: (5, 1), size = 8
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 6 6

[45]: (5, 0), size = 8
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 6 6

[49]: (5, 4), size = 8
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 6

[50]: (5, 5), size = 8
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

[60]: (0, 0), size = 9
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

60

kkkkkkya 5년 전 0

으어아 ... ㅜㅜ 감사합니다 ㅜㅜㅜㅜㅜㅜ 얼른 수정해야겠어요 감사합니다 !!!!

kkkkkkya 5년 전 0

댓글 달아주신분들 ㅜㅜ 너무너무 감사합니다 ! 제가 생각하지 못한게 많네요 ㅜㅜ 한 수 배워갑니다 !!! ♡♡

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

아기상어 예제4번과 시간초과 문제 도와주세요 ㅜㅜ

kkkkkkya 5년 전 1

kau_algoitsm 5년 전 1

kau_algoitsm 5년 전 3

kkkkkkya 5년 전 0

kkkkkkya 5년 전 0

djm03178 5년 전 3

kkkkkkya 5년 전 0

kkkkkkya 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말