[백준_16236]아기 상어 with Python, Java

백준(BOJ) 삼성 SW 역량 테스트 기출 문제 문제집: 아기 상어(골드 4)

문제 출처: https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

1. 알고리즘

  Python으로 먼저 풀어봤던 문제. 처음에 문제 읽고 로직 구상할 때 좀 막막하긴 했었다. 하지만 짜고나면 의외로 좀 심플한 듯? Java코드는 Python 코드랑 거의 동일함. 하지만 java를 최근에 풀었으니까 java로 풀이할 것...

  일단 물고기를 찾는 동작은 기본 BFS 동작. 다만 물고기가 없거나, 물고기 크기가 상어와 같을 때에만 route에 추가했다. 먹을 수 있는 물고기를 만나면 PriorityQueue에 삽입하고, 거기서 멈추도록 했다. 먹을 수 있는 물고기는 Node클래스에 설정해둔 정렬 기준(Comparable)에 따라 우선순위 큐에 자동으로 정렬됨.

  그렇게 먹을 수 있는 물고기 탐색을 마치고, 먹을 수 있는 물고기가 없었다면 엄마 상어를 호출(바로 종료). 먹을 수 있는 물고기가 있으면 큐에서 가장 앞의 값 하나를 뽑아(데이터 삽입 시 정렬되므로 정렬 필요 X) 상어에게 먹이는 동작 실행해줬다.

(이하 설명은 자바 코드 기준)

• Node 클래스 설계
  • 좌표 x, y값과 상어로부터의 거리 d 값을 필드로 함
  • Comparable로 정렬 기준 설정
    • d 비교
      • x비교
        • y비교
• N, field 데이터 입력받음
  • 입력받을 때 숫자 9를 만나면 babyShark 객체로 저장, 아기상어가 있던 칸은 0으로 초기화
• 먹을 수 있는 물고기를 담을 PriorityQueue 생성
• 먹을 수 있는 물고기가 없을 때까지 while 반복
  • eatFish메소드(BFS)로 field 탐색
    • 사방탐색
      • 좌표를 벗어나거나 이미 방문했던 곳이거나 칸의 물고기가 아기상어보다 크면 continue;
      • 물고기가 상어와 같은 크기이거나 칸이 비어있는 경우
        • 방문 처리, 아기 상어 이동
      • 물고기가 아기 상어보다 작은 경우
        • 방문 처리, fish 큐에 삽입, isEat 플래그 true;
    • isEat 플래그 반환
  • 플래그가 true(=먹을 물고기 있다)
    • 먹을 물고기(우선순위가 가장 높은 물고기) 선정
    • 물고기 거리만큼 시간에 더해줌
    • 먹은 물고기 개수 + 1
    • 먹은 물고기 수가 상어의 크기와 동일하면
      • 상어 크기 + 1
      • 먹은 물고기 수 초기화
    • 출발지 아기상어 위치 갱신
    • field의 아기상어 위치의 물고기는 먹었으므로 0 초기화
  • 플래그가 false(=먹을 물고기 없다 = 엄마 상어 호출 = while 반복 종료)
  • fish 큐 초기화
• while반복 종료 시 time 출력

 

2. 유의 사항

• 우선순위 지정
• 상어는 처음에 삭제해줘야 함. 숫자 9가 map에 남겨져 있으면 별도의 예외처리가 필요함
• 먹은 물고기 삭제

 

3. 어려웠던 점, 해결 방법

• 로직 자체가 처음 구상 때 헷갈렸음. 차근차근 탐색 범위부터 생각해서 구상함

 

4. 소스코드

상세 설명은 주석

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
//좌표, 거리 설정 Node 클래스 정의
class Node implements Comparable<Node>{
    int x;    //r좌표
    int y;    //c좌표
    int d;    //상어로부터의 거리
    
    Node(int x, int y, int d){    //생성자
        this.x = x;
        this.y = y;
        this.d = d;
    }
    
    @Override
    public int compareTo(Node o) {    //문제 조건에 맞는 정렬 기준(우선순위) 설정
        int result = this.d - o.d;            //거리 연산
        if(result == 0) {                    //거리 같을 시
            int subResult = this.x - o.x;        //r좌표 연산
            if(subResult == 0)                    //r좌표 같을 시
                return this.y - o.y;                //c좌표 연산 반환
            else
                return subResult;                //r좌표 연산 반환
        }
        return result;                        //d 연산 반환
    }
}
 
 
public class Main {
    
    static int N, size = 2;                //필드 크기, 상어 크기(초기값 2)
    static int[][] field;                //필드
    static Node babyShark;                //아기 상어(BFS 출발지)
    static PriorityQueue<Node> fish;    //물고기 후보 우선순위 큐
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        field = new int[N][N];
        for(int r=0; r<N; r++) {    //N*N번 반복해서 field 채움
            st = new StringTokenizer(br.readLine());
            for(int c=0; c<N; c++) {
                int temp = Integer.parseInt(st.nextToken());
                if(temp == 9) {        //아기 상어 발견!
                    babyShark = new Node(r, c, 0);     //babyShark 설정
                    temp = 0;                        //아기 상어 위치 0으로 세팅
                }
                field[r][c] = temp;    //field 채움
            }
        }
        
        fish = new PriorityQueue<>();
        int time = 0, eatCnt = 0;    //아기 상어가 물고기 먹는 시간, 아기 상어가 현재 사이즈에서 먹은 물고기 수
        while(true) {
            boolean isEat = eatFish(babyShark);    //물고기 후보 탐색
            if(isEat) {        //먹을 물고기가 있다.
                Node eat = fish.poll();    //가장 높은 우선순위 물고기 선정
                time += eat.d;            //물고기까지의 거리(=시간) 더하기
                eatCnt++;                //먹은 물고기 개수+1
                if(eatCnt == size) {    //현재 상어 크기 만큼 물고기를 먹었다면
                    size++;                    //상어 크기 +1
                    eatCnt = 0;                //먹은 개수 초기화
                }
                babyShark = eat;        //상어 객체를 지금 먹은 물고기 위치로 갱신
                babyShark.d = 0;        //거리 0 초기화
                field[babyShark.x][babyShark.y] = 0;    //먹은 물고기 위치 0초기화
                
            } else            //먹을 물고기가 없다.
                break;        //탐색 종료
            
            fish.clear();    //물고기 후보 큐 초기화
        }
        
        System.out.println(time);    //걸린 시간 출력
    }
 
    
    private static boolean eatFish(Node start) {    //BFS 탐색
        Queue<Node> route = new LinkedList<>();        //탐색 경로 큐
        boolean[][] visited = new boolean[N][N];    //방문 확인 배열
        route.add(start);                    //route에 출발지 추가
        visited[start.x][start.y] = true;    //출발지 방문 처리
        boolean isEat = false;                //먹을 수 있는 물고기 확인 flag 초기값 false 설정
        
        int[] dx = {-1, 1, 0, 0};    //사방탐색 좌표 설정
        int[] dy = {0, 0, -1, 1};
        while(!route.isEmpty()) {    //탐색 시작
            Node node = route.poll();    //현재 위치
            
            for(int idx=0; idx<4; idx++) {    //사방탐색
                int nx = node.x+dx[idx];    //다음 이동 좌표 계산
                int ny = node.y+dy[idx];
                
                if(nx<0 || nx>=N || ny<0 || ny>=N) continue;    //범위 밖인 경우 제외
                if(visited[nx][ny] || field[nx][ny] > size) continue;    //이미 방문했거나 해당 칸의 물고기가 상어보다 큰 경우
                
                if(field[nx][ny] == size || field[nx][ny] == 0) {    //칸의 물고기가 없거나 물고기 크기가 상어 크기와 같은 경우
                    visited[nx][ny] = true;        //방문 처리
                    route.add(new Node(nx, ny, node.d+1));    //이동
                } else if(field[nx][ny] < size) {        //상어 크기보다 물고기 크기가 작을 경우
                    visited[nx][ny] = true;        //방문 처리
                    fish.add(new Node(nx, ny, node.d+1));    //물고기 후보 추가
                    isEat = true;    //물고기 확인 flag true 설정
                }
            }
        }
        return isEat;    //먹을 수 있는 물고기가 있는 지 확인하는 flag 반환
    }
}

5. 고민

• PriorityQueue랑...그냥 LinkedList에 넣어서 sort 한 번씩 실행하는 거랑 속도 차이는 없었다...데이터가 많이 안들어가서 그런가

 

---

파이썬 코드

자바와 로직은 같음.

import sys
from collections import deque
 
 
def find_fish(start, size, graph):
    route = deque([start])
    visited = [[0]*N for _ in range(N)]
    visited[start[0]][start[1]] = 1
    fish_list = []
    fish_flag = False
 
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while route:
        x, y, d = route.popleft()
 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if 0<=nx<N and 0<=ny<N:
                #못 지나가
                if graph[nx][ny] > size:
                    continue
                #물고기가 없어! / 나랑 크기가 같아
                elif (graph[nx][ny] == 0 or graph[nx][ny] == size) and visited[nx][ny] == 0:
                    route.append([nx, ny, d+1])
                    visited[nx][ny] = 1
                #먹을 물고기가 있다
                elif graph[nx][ny] < size and visited[nx][ny] == 0:
                    fish_list.append((nx, ny, d+1))
                    visited[nx][ny] = 1
                    fish_flag = True
 
 
    return fish_flag, fish_list
 
 
if __name__=="__main__":
    N = int(*map(int, sys.stdin.readline().split()))
    space = []
    for r in range(N):
        temp = list(map(int, sys.stdin.readline().split()))
        space.append(temp)
        for c in range(N):
            if temp[c] == 9:
                start = [r, c, 0]
                space[r][c] = 2
 
    count, fish_count, size = 0, 0, 2
    while True:
        flag, fish_result = find_fish(start, size, space)
        if flag:
            #먹을 수 있는 물고기 정렬 > 가까운 위치 / 행 / 열
            fish_result = sorted(fish_result, key=lambda x: (x[2], x[0], x[1]))
            fish = fish_result[0]
            count += fish[2]
            fish_count += 1
            if fish_count == size:
                fish_count = 0
                size += 1
            space[start[0]][start[1]] = 0
            space[fish[0]][fish[1]] = size
            start = [fish[0], fish[1], 0]
        #엄마
        else:
            break
 
    print(count)