시작하기 전에
골드4의 난이도임에도 불구하고 개인적으로 많이 헤맸던 문제입니다. 오기가 생겨 이틀 정도 틈틈이 시간투자를 했지만 결국 검색을 통해 해결했습니다. 문제 설명이 꽤 복잡해 보이지만 한 번 자세히 보면 생각보다 간단한 문제이니 처음 읽을 때 유심히 보시는 것을 추천합니다.
문제 설명
-
상어는 9로 나타낸다.
-
아무 것도 없는 공간은 0으로 나타낸다.
-
1~6은 물고기의 크기를 나타낸다.
-
상어의 최초 크기는 2이다.
-
상어의 현재 크기보다 작은 물고기는 먹을 수 있다.
-
상어의 현재 크기만큼 물고기를 먹으면 상어의 크기는 1 증가한다.
-
상어와 크기가 같은 물고기는 먹을 수 없지만 지나 갈 수는 있다.
-
-
거리에 대한 우선 순위가 주어진다.
-
거리가 같다면 위쪽에 있는 물고기가 우선이다.
-
거리가 같고 위쪽에 있는 물고기가 여러 마리라면, 그 중 가장 왼쪽에 있는 물고기가 더 우선이다.
-
-
상어는 필드의 물고기를 먹을 수도 있고 못 먹을 수도 있다.
-
이 때, 최소 이동 횟수를 출력하라.
예시
위와 같은 예시가 있다고 생각합시다. 자, 어떤 루틴으로 상어가 움직여야 할까요?
우선, 동일한 거리에 두 개의 선택지가 있네요. 왼쪽과 위쪽.
위에서 언급했듯이 우선순위는 위쪽이 먼저입니다. 그래서 위쪽으로 이동하게 되겠죠.
상어의 크기가 2이고 자신의 크기보다 작은 물고기만 먹을 수 있기 때문에 크기 1의 물고기를 먹어야겠죠? (1,2)에 위치한 크기 1인 물고기를 먹으러 갑니다.
해당 위치의 물고기를 먹기 위해 2칸을 이동하면서 총 이동 횟수(시간)는 3회가 되었고,
먹은 물고기 수가 현재 상어의 크기와 같아지면서 상어는 크기가 1 커지게 됩니다.
크기가 커지면서 왼쪽과 위쪽에 먹을 수 있는 물고기가 생겼네요. 1회 이동때 언급했듯이 우선순위는 위쪽이므로 위의 물고기(1,1)를 먹게 되겠죠.
마찬가지로 아래쪽 2와 위쪽 2의 거리는 같지만 동일하게 위쪽 물고기(2,0)부터 먹습니다.
자 이제 아래에 위치한 크기가 2인 물고기(0,2)를 먹으러 갑시다.
다시 먹은 물고기 수와 현재 상어의 크기가 같아지면서 상어의 크기는 1 증가하게 됩니다.
이제 크기가 3인 물고기[(0,1), (0,0), (1,0)]를 순차적으로 먹으면 끝이겠네요.
자 이렇게 상어의 모험은 끝이 납니다.
어떤 방식으로 크기가 커지고, 어떻게 이동하는지 이해가 되셨나요?
자세한 로직은 제가 참고했던 블로그에 설명이 잘 되어 있으니 참고하시기 바랍니다.
소스코드 하단에 링크가 있습니다!
소스 코드
Python
##########################################################
import sys
from collections import deque
direction = [[0,1],[-1,0],[1,0],[0,-1]] #for BFS
input = sys.stdin.readline
def ip():return input().rstrip()
def lip():return list(ip())
def ips():return ip().split()
def ii():return int(input())
def mii():return map(int,ips())
def lmii():return list(mii())
##########################################################
n = ii()
field = list()
root = [-1,-1]
def bfs():
q = deque([[root[0],root[1]]])
visited = [[root[0],root[1]]]
answer = 0
shark_size = 2 # 초기 상어의 크기
shark_feed = 0 # 상어가 먹은 먹이의 수
shark_time = 0 # 상어가 움직인 시간(칸당 1 증가)
eat_flag = False # 먹이를 먹었는지 체크
# 먹이를 먹었다는 뜻은 가장 위 또는 좌측에 있는 먹이를 먹었으므로
# 더 이상 반복문(for _ in range(qSize))을 돌릴 필요가 없다는 뜻이다.
# 해당 반복문을 break하기 위한 용도로 쓰인다.
while q:
# 위쪽이 우선, 그 다음 왼쪽이 우선 정렬되어야 하므로
# y좌표(k[1])를 우선 정렬후 x좌표(k[0])를 기준으로 정렬한다.
if q:q = deque(sorted(q,key=lambda k:[k[1],k[0]]))
qSize = len(q)
for _ in range(qSize):
x,y = q.popleft()
#먹을 수 있는 범위
if 0<field[y][x]<shark_size:
field[y][x] = 0 #먹이를 먹었으므로 0으로 변경
shark_feed+=1 #먹은 먹이 수 증가
if shark_feed == shark_size:#크기 증가
shark_size+=1
shark_feed=0
# 먹이를 먹었으므로 새로운 탐색을 해야한다.
# 그래서 dq와 visited를 초기화 해준다.
q=deque()
visited = [[x,y]]
answer = shark_time
eat_flag=True
for dx,dy in direction:
nx,ny = x+dx,y+dy
# 필드 벗어나는 범위 체크, 방문 여부 체크
if 0<=nx<n and 0<=ny<n and not [nx,ny] in visited:
# 이동 가능한 범위
if field[ny][nx]<=shark_size:
q.append([nx,ny])
visited.append([nx,ny])
if eat_flag:
eat_flag=False
break
shark_time+=1
return answer
# 필드를 입력받고
# 동시에 상어의 위치를 찾고 저장한다.
for i in range(n):
tmp = lmii()
field.append(tmp)
if [-1,-1]==root:
for j in range(n):
if tmp[j]==9:
# 상어를 찾았다면 0으로 초기화 해주고
# 위치를 root에 등록해 준다.
root=[j,i]
field[i][j]=0
print(bfs())
# 소스코드 https://dailyheumsi.tistory.com/59 참고Java8
package boj16236;
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int field[][],visited[][],N,time,answer;
static boolean eat_flag = false;//먹이를 먹었는지 체크
static ArrayList<Pos> dq = new ArrayList<>();//상어의 정보를 관리하는 큐
static int[][] direction = new int[][] {{0,-1},{-1,0},{1,0},{0,1}};//BFS를 위한 방향 설정 상,좌,우,하
static int size= 2;//상어의 현재 크기
static int eat = 0;//상어가 먹은 먹이수(크기가 커지면 초기화)
static Pos shark = new Pos();//상어의 정보가 담긴 객체
static class Pos implements Comparable<Pos>{
int x,y; //상어의 현재 위치(좌표)
public Pos() {}
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Pos o) {
if(this.y>o.y)
return 1;
else if(this.y==o.y)
if(this.x>o.x)
return 1;
return -1;
}
}
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
field = new int[N][N]; //입력필드
visited = new int[N][N];//방문여부 체크하는 배열
for(int i =0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j =0; j<N;j++) {
field[i][j] = Integer.parseInt(st.nextToken());
if(field[i][j]==9) {//상어의 초기 위치 기록 및 초기화
field[i][j]=0;
shark.x=j;
shark.y=i;
}
}
}
dq.add(new Pos(shark.x,shark.y));
while(!dq.isEmpty()) {
Collections.sort(dq);
int qsize = dq.size();
for(int section=0;section<qsize;section++) {
Pos ci =dq.remove(0);//current info 현재 큐에 담겨있던 정보
//먹을 수 있는 크기인지 확인
int feed_size = field[ci.y][ci.x];
if(0<feed_size && feed_size<size) {//물고기인지 체크, 먹을 수 있는 크기인지 체크
field[ci.y][ci.x]=0;//먹이를 먹었으므로 먹이가 있던 필드 0으로 갱신
eat++; //먹이를 먹었으므로 상어의 먹은 횟수 1 증가
if(eat==size) {//상어의 크기가 커질 수 있는가?(먹은수==현재크기)
size++;
eat=0;//먹은 횟수는 반드시 초기화!!
}
//먹이를 먹었으므로(이동이 확실하므로)
//다른곳으로 이동하지 않기 때문에 큐와 방문기록을 초기화한다.
dq.clear();
visited = new int[N][N];
visited[ci.y][ci.x]=1;//현재 위치는 방문했으므로 체크
answer = time;
eat_flag = true;//먹이를 먹게되면
}
for(int dir[]:direction) {
int nx = ci.x+dir[0];//다음 X좌표
int ny = ci.y+dir[1];//다음 Y좌표
//필드 벗어나는지 체크, 이미 방문한 곳은 아닌지 체크, 크기 비교로 이동이 가능한 곳인지 체크
if(0<=nx&&nx<N&&0<=ny&&ny<N&&visited[ny][nx]==0&&field[ny][nx]<=size) {
dq.add(new Pos(nx,ny));
visited[ny][nx]=1;
}
}
if(eat_flag) {
eat_flag=false;
break;
}
}
time+=1;//1회 이동에 1초 증가
}
System.out.println(answer);
}
}