글 읽기 - 아기상어 질문

zo13258 5년 전 4

알고리즘을 풀면서 다른분에게 여쭤본다는 것이 큰 실례이고 귀찮은 점이라는 것을 알고 있습니다.

그래서 질문을 드리기 전에 죄송하다는 말씀을 먼저 드리고 시작하겠습니다.

제 질문은 다음과 같습니다.

아기상어 예제에서 4번 예제가 왜 60이 나오는지

전혀 이해가 되지 않습니다.

실제로 프로그램을 돌려봐도, 직접 손으로 풀어도 56이 나오는데

제가 어느 부분에서 잘못 이해를 한 것인지 코드를 통해 여쭤보고 싶습니다.

문제를 bfs로 풀었고, 탐색 순서는 상좌우하입니다.

소스코드를 첨부하오니 확인 부탁드리겠습니다. 감사합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	private static int mapSize;
	private static int[][] map;
	
    //상어의 x, y, 무게 입니다.
	private static int mainX;
	private static int mainY;
	private static int mainW;
    
    //상어가 먹은 물고기의 양
	private static int eaten;
	
    //남아있는 물고기(상어 제외)의 양
	private static int fishNum;
	
	public static void main(String args[]) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		eaten = 0;
		fishNum = 0;
		mapSize = Integer.parseInt(br.readLine());
		map = new int[mapSize][mapSize];
		for(int j = 0; j < mapSize; j++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int k = 0; k < mapSize; k++) {
				int weight = Integer.parseInt(st.nextToken());
				map[j][k] = weight;
				if(weight == 9) {
					mainY = j;
					mainX = k;
					mainW = 2;
					map[j][k] =0;
				} else if (weight > 0) {
					fishNum++;
				}
			}
		}
		System.out.print(run());
		
	}
	
	private static int run() {
		
		int ret = 0;
		
		while(mainY != -1 && fishNum > 0) {
            //다음에 먹을 물고기를 찾고, 그 좌표와 먹기 위해 필요한 이동수
			int[] targetNMove = search();
			mainY = targetNMove[0];
			mainX = targetNMove[1];
//			System.out.println("좌표 : " + mainY + " " + mainX);
			ret += targetNMove[2];
			fishNum--;
			if(eaten == mainW) {
				eaten = 0;
				mainW++;
//				System.out.println("level : " + mainW);
			}
		}
		return ret;
		
	}
	
	private static int[] search() {
		int[] ret = new int[] {-1, -1, 0};
		map[mainY][mainX] = 0;
		
		ArrayList<Integer> xs = new ArrayList<>();
		ArrayList<Integer> ys = new ArrayList<>();
		ArrayList<Integer> moves = new ArrayList<>();
		
		xs.add(mainX);
		ys.add(mainY);
		moves.add(0);
		
		boolean[][] visited = new boolean[mapSize][mapSize];
		visited[mainY][mainX] = true;
		
		
		while(!xs.isEmpty()) {
			int x = xs.get(0);
			int y = ys.get(0);
			int move = moves.get(0);
			xs.remove(0);
			ys.remove(0);
			moves.remove(0);
            
            //상 탐색
			
			int nextY = y - 1;
			int nextX = x;
			
			if(y > 0 && !visited[nextY][nextX] && map[nextY][nextX] <= mainW) {
				if(map[nextY][nextX] < mainW && map[nextY][nextX] != 0) {
					ret[0] = nextY;
					ret[1] = nextX;
					ret[2] = move + 1;
					eaten++;
					return ret;
				}
				visited[nextY][nextX] = true;
				xs.add(nextX);
				ys.add(nextY);
				moves.add(move + 1);
			}
			
            //좌 탐색
            
			nextY = y;
			nextX = x - 1;
			
			if(x > 0 && !visited[nextY][nextX] && map[nextY][nextX] <= mainW) {
				if(map[nextY][nextX] < mainW && map[nextY][nextX] != 0) {
					ret[0] = nextY;
					ret[1] = nextX;
					ret[2] = move + 1;
					eaten++;
					return ret;
				}
				visited[nextY][nextX] = true;
				xs.add(nextX);
				ys.add(nextY);
				moves.add(move + 1);
			}
			
            //우 탐색
            
			nextY = y;
			nextX = x + 1;
			
			if(x < mapSize - 1 && !visited[nextY][nextX] && map[nextY][nextX] <= mainW) {
				if(map[nextY][nextX] < mainW && map[nextY][nextX] != 0) {
					ret[0] = nextY;
					ret[1] = nextX;
					ret[2] = move + 1;
					eaten++;
					return ret;
				}
				visited[nextY][nextX] = true;
				xs.add(nextX);
				ys.add(nextY);
				moves.add(move + 1);
			}
			
            //하 탐색
            
			nextY = y + 1;
			nextX = x;
			
			if(y < mapSize - 1 && !visited[nextY][nextX] && map[nextY][nextX] <= mainW) {
				if(map[nextY][nextX] < mainW && map[nextY][nextX] != 0) {
					ret[0] = nextY;
					ret[1] = nextX;
					ret[2] = move + 1;
					eaten++;
					return ret;
				}
				visited[nextY][nextX] = true;
				xs.add(nextX);
				ys.add(nextY);
				moves.add(move + 1);
			}
			
			
		}
		
		return ret;
		
	}
}

jh05013 5년 전 12

예제 4에서 물고기를 먹는 순서는 다음과 같이 나옵니다.

입력:
6
4 3 2 3 4
3 2 3 4 5
2 9 5 6 6
1 2 3 4 5
2 1 6 5 4
6 6 6 6 6

순서:
10 6 5 7 21
9 4 8 19 20
13 0 18 23 22
1 3 17 24 25
16 2 28 27 26
31 30 29 33 34

zo13258 5년 전 7

답변 감사드립니다.

제가 짠 코드로 돌려보니 이렇게 나옵니다.

입력 :

5 4 3 2 3 4

4 3 2 3 4 5

3 2 9 5 6 6

2 1 2 3 4 5

3 2 1 6 5 4

6 6 6 6 6 6

순서 :

35 11 6 5 12 13

10 7 4 15 14 33

9 8 0 16 34 32

28 1 3 17 18 19

27 26 2 22 21 20

29 25 24 23 30 31

맨 처음 순서가 바뀌는 구간은 6에서 7으로 넘어가는 구간이었습니다.

제 부족함을 알게 되었습니다. 감사합니다.

sotter1020 5년 전 1

저 혹시 이거 해결 하셨나요?

저도 똑같이 풀어서 문제점을 발견했는데..

어떻게 해결해야 할지 감이 안잡히네요 ㅠㅠ

아니면 다시 짜셨나요? 거기서 bfs에서 예외처리 해주셨나요?

lonecitizen 5년 전 6

@sotter1020

한달 전이라 이걸 읽으실지는 모르겠지만, BFS에서 방향벡터 쓰셔서 하는 경우에는 발견 즉시 물고기를 먹지 않게 하면 해결됩니다.

우선 먹을 수 있는 물고기의 위치를 표현하는 배열하나를 만드시고, 전체 탐색을 하셔서 해당 배열을 채워줍니다.

그다음에 for문 2개 row col순으로 돌려서 가장 먼저 발견되는 위치가 맨 위, 맨 왼쪽이므로 발견 즉시 먹고 count올리고 크기만큼 먹으면 크기 키워주고 등등 하시면 됩니다.

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

문제

문제

출처

ICPC

아기상어 질문

zo13258 5년 전 4

jh05013 5년 전 12

zo13258 5년 전 7

sotter1020 5년 전 1

lonecitizen 5년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말