알고리즘 포스팅 진짜 오랜만에 해보는 거 같다.
삼성 대학생 인턴에 서류합격해서 SW 역량테스트를 준비해야된다.
그런데 C++하다가 요새 파이썬만 하니까 C++도 까먹고 파이썬도 잘 알지는 못하는 그런 애매한 상황이 되어버렸다,,,! 그래서 포스팅하면서 새롭게 알게 된 점도 좀 정리를 하려고 포스팅을 다시 시작했다.
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
문제를 읽자마자 최단 거리 -> BFS를 생각했다.
BFS를 돌면서 가장 가까운 물고기의 위치를 찾고, 그 위치로 이동하는 것을 반복해야한다.
우선 class를 이용해서 상어의 위치와 크기 , 잡아먹은 물고기 수를 만들어준다.
잡아먹은 물고기의 수가 필요한 이유는 잡아먹은 물고기의 수가 상어의 크기와 같아지면 상어의 크기가 업그레이드 되기 때문!
class Shark:
def __init__(self, x ,y , size):
self.x = x # 현재 상어의 행
self.y = y # 현재 상어의 열
self.size = size # 현재 상어의 크기
self.num = 0 # 잡아먹은 물고기 수
그 다음에 어장의 상태를 입력으로 받으면서 상어의 위치를 저장하고, 꼭꼭 어장 위 상어가 있는 자리를 0으로 만들어줘야한다 😂 이걸 안하면 계속 9로 남게 되어서 상어의 크기보다 크다고 인식돼서 넘어갈 수가 없고, 뺑뻉 돌아서 가게 된다. 이거 때문에 시간 30분 날림 ㅜㅜ
board = []
for row in range(N):
board.append(list(map(int, input().split(' '))))
for col in range(N):
if board[row][col] == 9:
shark = Shark(row,col,2)
board[row][col] = 0
아래에서터가 핵심이다.
1 ) 보드 내에 존재해야 함
2 ) 방문한 적이 없어야 함
3 ) 그 칸에 존재하는 물고기가 상어보다 작거나 같아야 함
이 3가지 조건을 다 만족시켜야 그 다음칸으로 넘어갈 수 있다. 이걸 확인하는 check 함수를 만들어준다.
def check(x , y , temp_board) :
# 1) 보드 내 , 2) 방문한 적 없어야 하고 , 3) 그 칸에 물고기가 있다면 자기보다 작거나 같아야 됨
if -1 < x < N and -1 < y < N and temp_board[x][y] == 0 and board[x][y] <= shark.size :
return True
return False
이 조건을 만족시킨다면 물고기와의 몸집을 비교해야한다.
물고기의 크기와 상어의 크기가 같다면 지나가는 것밖에 못하기 때문에 큐에 추가를 해준다.
물고기의 크기가 상어의 크기보다 작다면 잡아먹는 물고기의 후보군이 될 수 있다.
이 때는 큐에 추가해서 그 다음의 상하좌우를 봐도 거리가 더 멀기 때문에 큐에 추가해주지 않는다.
그리고 이 물고기까지의 거리와 최소거리를 비교해준다.
최소거리보다 이 물고기까지의 거리가 작다면 무조건 이 물고기를 선택하게 된다.
이때 최소거리 , 물고기의 위치를 업데이트한다.
최소거리와 이 물고기까지의 거리가 같다면 더 위쪽에 있는지, 행이 같다면 더 왼쪽에 있는 지를 확인 후 업데이트해준다.
만약 최소행, 열이 처음 설정한 값과 같다면 더 이상 잡아먹을 물고기가 없단 뜻으로 False를 리턴해준다.
처음 설정한 값과 다르다면 잡아먹은 물고기가 있단 뜻이고 이동했단 뜻이다.
걸린 시간과 상어의 위치, 상어가 잡아먹은 물고기의 수를 업데이트 해준다.
물고기는 잡아먹혔으므로 board 위 물고기가 위치하던 자리는 0이 된다.
업데이트 된 상어가 잡아먹은 물고기의 수가 상어의 크기와 같다면 상어의 크기를 하나 키워주고, 잡아먹은 물고기의 수를 0으로 초기화해준다.
def find_fish(row,col):
temp_board = [[0]*N for _ in range(N)]
min_distance = 1e6
min_r , min_c = 1e6 , 1e6
q = deque([[row,col]])
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if check(nx,ny,temp_board):
temp_board[nx][ny] = temp_board[x][y] + 1
# 자기 몸집보다 작은 녀석이 있다면 그 거리로 확정 + que에 넣어줄 필요 없음
if 0 < board[nx][ny] < shark.size :# 자기보다 몸집이 작으면
# 근데 최소 거리보다 멈 -> 가치가 없다.
# 최소 거리보다 짧거나 같다? 그러면 눈 여겨 볼 필요가 있지
if min_distance > temp_board[nx][ny] : # 짧으면 무조건
min_r , min_c , min_distance = nx , ny , temp_board[nx][ny]
elif min_distance == temp_board[nx][ny] and ( min_r > nx or ( min_r == nx and min_c > ny)):
min_r , min_c , min_distance = nx , ny , temp_board[nx][ny]
else : # 자기랑 몸집이 같으면 지나가야지 # 어차피 check에서 몸집이 더 큰 애들 걸러짐
q.append([nx,ny])
global time
if min_r == 1e6 and min_c == 1e6 : # 자기보다 작은 물고기가 이제 업슴
return False
time += min_distance
board[min_r][min_c] = 0
shark.x , shark.y = min_r , min_c
shark.num += 1
if shark.num == shark.size :
shark.num = 0
shark.size += 1
return True
전체 코드는
import sys
sys.setrecursionlimit(1e6)
from collections import deque
import copy
N = int(input())
dx = [1,-1,0,0]
dy = [0,0,1,-1]
global time
time = 0
class Shark:
def __init__(self, x ,y , size):
self.x = x # 현재 상어의 행
self.y = y # 현재 상어의 열
self.size = size # 현재 상어의 크기
self.num = 0 # 잡아먹은 물고기 수
board = []
for row in range(N):
board.append(list(map(int, input().split(' '))))
for col in range(N):
if board[row][col] == 9:
shark = Shark(row,col,2)
board[row][col] = 0
def check(x , y , temp_board) :
# 1) 보드 내 , 2) 방문한 적 없어야 하고 , 3) 그 칸에 물고기가 있다면 자기보다 작거나 같아야 됨
if -1 < x < N and -1 < y < N and temp_board[x][y] == 0 and board[x][y] <= shark.size :
return True
return False
def find_fish(row,col):
temp_board = [[0]*N for _ in range(N)]
min_distance = 1e6
min_r , min_c = 1e6 , 1e6
q = deque([[row,col]])
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if check(nx,ny,temp_board):
temp_board[nx][ny] = temp_board[x][y] + 1
# 자기 몸집보다 작은 녀석이 있다면 그 거리로 확정 + que에 넣어줄 필요 없음
if 0 < board[nx][ny] < shark.size :# 자기보다 몸집이 작으면
# 근데 최소 거리보다 멈 -> 가치가 없다.
# 최소 거리보다 짧거나 같다? 그러면 눈 여겨 볼 필요가 있지
if min_distance > temp_board[nx][ny] : # 짧으면 무조건
min_r , min_c , min_distance = nx , ny , temp_board[nx][ny]
elif min_distance == temp_board[nx][ny] and ( min_r > nx or ( min_r == nx and min_c > ny)):
min_r , min_c , min_distance = nx , ny , temp_board[nx][ny]
else : # 자기랑 몸집이 같으면 지나가야지 # 어차피 check에서 몸집이 더 큰 애들 걸러짐
q.append([nx,ny])
global time
if min_r == 1e6 and min_c == 1e6 : # 자기보다 작은 물고기가 이제 업슴
return False
time += min_distance
board[min_r][min_c] = 0
shark.x , shark.y = min_r , min_c
shark.num += 1
if shark.num == shark.size :
shark.num = 0
shark.size += 1
return True
while True:
flag = find_fish(shark.x , shark.y)
if not flag : break
print(time)
알게 된 사실
1. 재귀를 늘릴 때 아래 코드를 많이 쓰는데 절대 1e6이런 식으로 쓰면 안된다.
저기는 무조건 int형만 받기 때문이다.
sys.setrecursionlimit(100000)
2. deque에 익숙하지가 않은데,,,
deque의 append , pop은 모두 오른쪽에서 빠져나간다.
que의 역할을 하려면 append로 뒤에 추가, leftpop으로 앞에서 빠져나가게 해주어야 한다.