developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • ARIMA모형
  • 삼성코테자바꿀팁
  • 코테파이썬
  • 시계열
  • 삼성코테파이썬
  • 통계분석
  • MA모형
  • SW역량테스트파이썬풀이
  • 데이터분석
  • 시계열분석
  • c++ 빌더 패턴
  • 삼성코테구현풀이
  • 삼성코테파이썬풀이
  • BOJ파이썬풀이
  • 백준파이썬풀이
  • 삼성코테파이썬준비
  • c++디자인패턴
  • 삼성코테기출
  • 통계학
  • 삼성코테준비
  • 카카오코테java풀이
  • Arima
  • 삼성코테구현문제추천
  • 운영체제인터럽트
  • SW역량테스트파이썬
  • 삼성코테기출자바풀이
  • AR모형
  • 삼성코테자바준비
  • 카카오코테
  • 삼성코테자바풀이

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 아기 상어 16236번 (JAVA)

2022. 4. 29. 22:05

❓ 문제 - 백준 아기 상어 16236번 - JAVA 풀이법

출처 

(https://www.acmicpc.net/problem/16236)

 

 

📝 문제해결법

1. 이 문제는 BFS + 구현으로 풀었다.

  • 아기상어는 현재위치에서 BFS를 통해 거리가 가장 가깝고, 거리가 같으면 행이 가장 작고, 행이 같으면 열이 작은 물고기를 구한다. 만약 BFS에서 반환되는 값이 NULL, 즉 먹을 수 있는 물고기가 없으면 종료하고 값을 출력한다.
  • BFS내에서 아기상어는 자기자신보다 작은 사이즈의 물고기에 대한 정보를 우선순위큐 pq에 넣고, 자기 자신과 크기가 같거나 자기 자신보다 크기가 작은 물고기를 지나갈 수 있으므로 지나다니면서 먹을 수 있는 물고기를 찾아 다닌다.
  • 우선순위 큐에서 하나 꺼낸 게 아기상어가 먹으러가는 물고기 이므로 해당 물고기를 먹고, 아기상의 위치를 그 물고기의 위치로 변경시켜준다. 
  • 만약 현재까지 먹은 물고기의 갯수가 현재 아기상어의 크기만큼이라면 아기상어의 크기는 1증가하고 현재까지 먹은 물고기 수를 0으로 리셋해준다.

 

 

💻 소스코드

// BOJ - 아기상어(16236번)
// 구현 + BFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main_16236{
	public static int n;
	public static int s_x, s_y, s_size;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static int[][] map;
	public static class Fish implements Comparable<Fish>{
		int x;
		int y;
		int dis;

		public Fish(int x, int y, int dis) {
			this.x = x;
			this.y = y;
			this.dis = dis;
		}
		@Override
		public int compareTo(Fish o) {
			// TODO Auto-generated method stub
			if(this.dis==o.dis) {
				if(this.x == o.x) {
					return this.y- o.y;
				}
				return this.x - o.x;
			} 
			return this.dis - o.dis;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		s_size = 2;
		for(int i=0;i<n;i++) {
			String[] data = br.readLine().split(" ");
			for(int j=0;j<n;j++) {
				map[i][j] = Integer.parseInt(data[j]);
				if(map[i][j] == 9) {
					map[i][j] = 0;
					s_x = i;
					s_y = j;
				} 
			}
		}
		
		int time = 0;
		int cnt = 0;
		while(true) {
			Fish fish = bfs();

			if(fish == null) {
				break;
			} else {
				map[fish.x][fish.y] = 0;
				s_x = fish.x;
				s_y = fish.y;
				cnt++;
				time += fish.dis;
				if(cnt == s_size) {
					cnt = 0;
					s_size++;
				} 
			}
	
		}
		
		System.out.println(time);

	}
	
	public static Fish bfs() {
		PriorityQueue<Fish> pq = new PriorityQueue<>();
		
		boolean[][] visited = new boolean[n][n];
		Queue<Fish> q = new LinkedList<>();
		q.add(new Fish(s_x, s_y, 0));
		visited[s_x][s_y] = true;
		int move_cnt = 0;
		while (!q.isEmpty()) {
			Fish fish = q.poll();

			for(int d=0;d<4;d++) {
				int nx = fish.x + dx[d];
				int ny = fish.y + dy[d];
				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
					if(!visited[nx][ny] & map[nx][ny] <= s_size) {
						q.add(new Fish(nx, ny, fish.dis+1));
						visited[nx][ny] = true;
						if(map[nx][ny] != 0 && map[nx][ny] < s_size) {
							pq.add(new Fish(nx, ny, fish.dis+1));
						}
					}
				}
			}
			
		}
		if(pq.isEmpty()) {
			return null;
		}
		return pq.poll();
	}

}

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 낚시왕 17143번 (JAVA)  (0) 2022.04.29
BOJ - 미세먼지 안녕! 17144번 (JAVA)  (0) 2022.04.29
BOJ - 인구 이동 16234번 (JAVA)  (0) 2022.04.29
BOJ - 나무 재테크 16235번 (JAVA)  (0) 2022.04.22
BOJ - 큐빙 5373번 (JAVA)  (0) 2022.04.22
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 낚시왕 17143번 (JAVA)
    • BOJ - 미세먼지 안녕! 17144번 (JAVA)
    • BOJ - 인구 이동 16234번 (JAVA)
    • BOJ - 나무 재테크 16235번 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바