문제
[골드3]
https://www.acmicpc.net/problem/16236
해설 없이 스스로 풀었나요?
O
시간은 오래걸렸으나 .. 시간초과 이슈를 해결하고 성공해냄!
문제 요약
- 처음 상어의 크기는 2이다.
- 상어의 크기보다 작은 물고기만 먹을 수 있다.
2-1. 상어의 크기와 같은 물고기는 지나가는 것만 가능하다. - 먹을 수 있는 물고기가 한마리면 그 물고기를 먹으러 간다.
3-1. 먹을 수 있는 물고기가 여러마리인 경우
3-1-1. 먹을 수 있는 물고기까지의 거리가 다른 경우, 가장 가까운 물고기를 먹으러 간다.
3-1-2. 먹을 수 있는 물고기까지의 거리가 같은 경우, 가장 위의 물고기를 먹고 그런 물고기가 여러마리면 가장 왼쪽에 있는 물고기를 먹으러 간다. - 상어의 크기와 같은 개수의 물고기를 먹으면 크기가 1 증가한다.
- 상어 크기가 2인 경우 2마리 물고기를 먹어야 크기 증가
- 종료조건 : 남아있는 물고기 중 먹을 수 있는 물고기가 없을 때
아이디어
입력을 받은 후 반복문을 돌며 먹을 수 있는 물고기를 찾는 함수(find_possible),
현재 상어의 위치에서 bfs를 통해 그래프 각 위치까지의 경로 계산하는 함수(bfs),
가장 가까운 위치의 먹을 수 있는 물고기를 찾는 함수(find_eat)를 반복하며
종료 전까지의 시간을 계산하려고 하였다.
세개의 함수는 bfs, 이중 포문 등 시간복잡도가 컸기에 매 반복문마다 이를 반복하니 시간초과가 떴고,
생각해보니 find_possible 부분을 굳이 따로 진행하며 시간복잡도를 높일 필요가 없다는 사실을 깨달았다.
따라서 이 부분을 find_eat 에서 조건을 추가하며 구현했다.
현재 위에서부터 아래로, 그 안에서는 왼쪽에서부터 오른쪽으로 (3-1-2 조건에 맞춰)
상어의 위치로부터 가장 가까운 것 중(cost 값이 최소), 먹을 수 있는 물고기(상어의 사이즈보다 작고, 1보다는 크거나 같은)를 찾아 상어의 이동 좌표를 결정했다.
상어가 이동하면서 물고기를 먹으면 해당 자리는 물고기의 크기에서 상어가 있음을 나타낼 수 있도록 9로 변경해주었고, 다시 다음 위치로 이동하면 그 자리는 0으로 변경하도록 하였다.
-> 9로 나타낼 필요X
어차피 상어가 어디있는지는 loc_x, loc_y에 담겨 있고 bfs에서 거리를 계산할 때 처음 상어의 위치는 0으로 바꾸며 방문처리하므로 9와 0으로 구분할 필요 없이 상어가 지난 자리는 모두 그래프 값을 0으로 바꾸면 된다!
무튼 이 부분을 제대로 구현 안해서 처음에 출력값이 조금씩 다르게 떴다..
추가로, 이동이 가능한 것과 먹을 수 있는 것의 구분을 어떻게 해야되는지에 대한 고민이 있었다.
나는 상어의 위치로부터 각 좌표까지의 거리를 cost라는 이차원배열에 나타냈고, 일단 먹을 수 있는 것은 고려하지 않고 거리 값만 bfs를 통해 cost에 기록하였다.
이후 상어가 이동할 좌표(가장 가까운 거리,cost 배열 중 최솟값)를 찾을 때 그 좌표에 먹을 수 있는 물고기가 있는지를 조건을 통해 구현하였다.
풀이
내가 성공한 코드(시간초과 해결), 시간초과 뜬 코드, 이코테 답안 순으로 적혀있다.
- 성공한 코드
구글링, 이코테 답안으로 공부해본 후, 주석으로 코멘트를 몇개 달았다. (느낌표로 표시함)
# 시간초과 해결
# 먹을 수 있는 물고기를 찾는 함수(find_possible) 내용을
# bfs에서 현재 상어 위치에서 cost 값 찾은 후 먹을 물고리를 찾는 함수(find_eat)에 합침.
import sys
from collections import deque
N = int(input())
graph = [] # 상어 및 물고기 위치
for _ in range(N):
graph.append(list(map(int, sys.stdin.readline().split())))
loc_x, loc_y = 0, 0 # 상어의 위치
size = 2 # 상어의 크기
time = 0
ate = 0
q = deque()
# 처음 상어의 위치 찾기
for i in range(N):
for j in range(N):
if graph[i][j] == 9:
loc_x = i
loc_y = j
# bfs 상하좌우 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
# 현재 상어의 위치는 loc_x, loc_y, 크기는 size. 이동하면서 상어의 위치가 바뀌므로 graph에서 9로 표기!!!**
cost[loc_x][loc_y] = 0 # 상어의 위치는 비용그래프에서 값 바꿔줘야 함. -> 0으로 표현
q.append((loc_x, loc_y))
while q:
x, y = q.popleft()
for i in range(4): # 상어 상하좌우로 이동시키며 가능한지 확인 1. 범위 내인지 2. 이동가능한지
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= N or ny >= N or (nx == loc_x and ny == loc_y): # 범위내인지 확인, 현재 상어의 위치도 continue
continue
# 방문하지 않았는지 조건 추가, ! graph 값이 9인 것은 이미 cost값을 0으로 처리했기 때문에 조건 필요 없음.
if graph[nx][ny] <= size and cost[nx][ny] == 1e9 and graph[nx][ny] != 9:
dist = cost[x][y] + 1 # ! 어차피 첫 방문이므로 모든 값이 if문을 만족함. 따라서 바로 갱신해주어도 됨.
if dist < cost[nx][ny]:
cost[nx][ny] = dist
q.append((nx, ny))
# 현재 cost 배열에는 먹을 물고기 뿐 아니라 이동가능경로(0, size와 똑같은 값)도 포함돼있으므로 먹을 수 있는 물고기를 찾아야 함
def find_eat():
global loc_x, loc_y # 외부에서 선언한 변수를 함수 속에서 호출하고 싶으면 ...
# 전역변수를 지역변수로 호출해 is not accessed 오류 발생 -> 함수 내부에 global '변수명' 추가
small = 1e9
# * 먹을 수 있는 것 찾기 전에(이동 전에) 현재 상어의 위치 그래프 값 0으로 변경
graph[loc_x][loc_y] = 0 # ! while문에서 상어 위치값을 9로 표기했을 때만 필요한 과정임
for i in range(N):
for j in range(N): # 순차탐색함으로써 만약 최솟값이 여러개이면 가장 위, 왼쪽부터 이동하도록
if cost[i][j] < small and (graph[i][j] < size and graph[i][j] >= 1):
small = cost[i][j]
loc_x, loc_y = i, j # 먹을 수 있는 물고기 중 가장 가까운 곳의 물고기 찾아서 현재 상어의 위치 변경
return False if small == 1e9 else True # 먹을 수 있는 물고기가 없는 경우
while True:
cost = [[1e9 for _ in range(N)] for _ in range(N)] # 매번 이동할 때마다 초기화
# 현재 상어 위치(x, y)에서 cost 계산
bfs()
# cost 값 중, 먹을 수 있는 물고기인지 체크하며 최소 찾기
check = find_eat()
if check:
# 이동할 곳을 찾았으니, 물고기 먹고 ate 증가, 그래프 값 0으로 변경XX -> ** 9로 변경!~!, 이동한 거리(시간)만큼 time 증가
ate += 1
time += cost[loc_x][loc_y]
graph[loc_x][loc_y] = 9 # ! 이 값을 사용할 일이 없으므로 0으로 저장해도 됨.
if ate == size: # 상어가 자신의 크기와 같은 수의 물고기를 먹었다면
size += 1
ate = 0
# print("time {}, size {}, 상어 현재 위치 {}, {}, 먹은 물고기 ate {}".format(time, size, loc_x, loc_y, ate))
else:
break
print(time)- 시간초과 난 코드
이거는 시간초과가 떴던, 먹을 수 있는 물고기를 찾는 함수를 따로 돌려 이중포문을 매번 쓸데없이 수행하는 코드이다.
중간중간 코드를 짜며 고민했던 흔적들도 적혀있다.. ^-6..
# 시간초과
import sys
from collections import deque
N = int(input())
graph = [] # 상어 및 물고기 위치
for _ in range(N):
graph.append(list(map(int, sys.stdin.readline().split())))
# 이동하면서 상어의 위치를 9로 표기하기
# 1. 자기 크기보다 작은 물고기 큐에 넣기. -> 큐에 넣은 거 까지의 거리 구하기. -> X
# -> 이동할 수 있는지 판단 : 자기 자신과 같거나 작은 물고기까지만 밟을 수 있음을 고려
# 물고기 먹으면 해당 자리는 0으로 변경하기 ** 값이 0인 칸은 물고기가 아니므로 먹은 것이 아니다.
loc_x, loc_y = 0, 0 # 상어의 위치
size = 2 # 처음 상어 크기는 2
time = 0
count = 0
q = deque()
# 처음 상어의 위치 찾기
for i in range(N):
for j in range(N):
if graph[i][j] == 9:
loc_x = i
loc_y = j
# 혹시 1번을 안하고 바로 bfs.. 하나? **"상하좌우"** 이동하면서 가까운 거부터 먹는거지
# 1. 먹을 수 있는 물고기 찾기 2. 가장 가까운 물고기 찾기 3. 가장 가까운 게 여러개이면 기준에 부합하게
def find_possible():
p_count = 0
for i in range(N):
for j in range(N):
if graph[i][j] < size and graph[i][j] >= 1: # 1 이상 상어 크기 미만
possible[i][j] = 1
p_count += 1
if p_count == 0: # 먹을 수 있는 물고기가 없으면
return False
elif p_count >= 1: # 먹을 수 있는 물고기가 하나면 .. 하나여도 bfs 실시해야 하네.. ㅋ
return True
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 고민1. 이동이 가능한 것과 먹을 수 있는 것의 구분은 어떻게.. 일단 구분짓지말고 짧은 거 찾을 때 무게 다시 비교?
def bfs():
# 현재 상어의 위치는 loc_x, loc_y, 크기는 size. 현재 상어의 위치가 계속 바뀌니까 거거 명확히 표현
cost[loc_x][loc_y] = 0 # 상어의 위치는 비용그래프에서 -1로 표현
q.append((loc_x, loc_y))
while q:
x, y = q.popleft()
# print(x, y)
for i in range(4): # 상어 상하좌우로 이동시키며 가능한지 확인 1. 범위 내인지 2. 이동가능한지
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= N or ny >= N or (nx == loc_x and ny == loc_y): # 범위내인지 확인, 현재 상어의 위치도 continue
continue
# 방문하지 않았는지 조건 추가
if graph[nx][ny] <= size and cost[nx][ny] == 1e9 and graph[nx][ny] != 9: # 이동한 위치의 물고기 크기가 상어의 크기와 같다면 이동만 가능
dist = cost[x][y] + 1
if dist < cost[nx][ny]:
cost[nx][ny] = dist
q.append((nx, ny))
# elif graph[nx][ny] < size and cost[nx][ny] == 1e9: # 이동한 위치의 물고기 크기가 상어의 크기보다 작다면 먹을 수 있음
# dist = cost[x][y] + 1
# if dist < cost[nx][ny]:
# cost[nx][ny] = dist
# q.append((nx, ny))
# 현재 cost 배열에는 먹을 물고기 뿐 아니라 이동가능경로(0, size와 똑같은 값)도 포함돼있음
# possible 배열과 함께 비교후 먹을 물고기를 찾아야 함
def find_eat():
global loc_x, loc_y # 외부에서 선언한 변수를 함수 속에서 호출하고 싶으면 ...
# 전역변수를 지역변수로 호출해 is not accessed 오류 발생 -> 함수 내부에 global '변수명' 추가
small = 1e9
# * 먹을 수 있는 것 찾기 전에(이동 전에) 현재 상어의 위치 그래프 값 0으로 변경
graph[loc_x][loc_y] = 0
# print(possible)
# print(cost)
for i in range(N):
for j in range(N): # 순차탐색함으로써 만약 최솟값이 여러개이면 가장 위, 왼쪽부터 이동하도록 <- 왼쪽이 먼저다. 위부터 하도록.. 다시짜야됨!
# print(cost[i][j], small)
if cost[i][j] < small and possible[i][j] == 1:
small = cost[i][j]
loc_x, loc_y = i, j # 먹을 수 있는 물고기 중 가장 가까운 곳의 물고기 찾아서 현재 상어의 위치 변경
while True:
cost = [[1e9 for _ in range(N)] for _ in range(N)] # 매번 이동할 때마다 초기화 - 시간초과 안뜰까?
possible = [[0 for _ in range(N)] for _ in range(N)]
# 현재 상어 위치(x, y)에서 먹을 수 있는 물고기 찾기
check = find_possible() # find_possible을 꼭 해야 하는가 ?
if check:
bfs()
find_eat()
# 이동할 곳을 찾았으니, 물고기 먹고 count 증가, 그래프 값 0으로 변경 ** 9로 변경!~!, 이동한 거리(시간)만큼 time 증가
count += 1
time += cost[loc_x][loc_y]
graph[loc_x][loc_y] = 9
# print(graph)
if count == size: # 상어가 자신의 크기와 같은 수의 물고기를 먹었다면
size += 1
count = 0
# print("time {}, size {}, 상어 현재 위치 {}, {}, 먹은 물고기 count {}".format(time, size, loc_x, loc_y, count))
# print()
# print()
else: # 먹을 수 있는 물고기가 없으면
break
print(time)
- 이코테 답안
이코테 답안 99.8% 고대로 코드.
import sys
from collections import deque
INF = 1e9 # 무한을 뜻함, 10억으로 설정
N = int(input())
graph = [] # 상어 및 물고기 위치
for _ in range(N):
graph.append(list(map(int, sys.stdin.readline().split())))
# 상어의 크기와 현재 위치 <- global을 붙일 필요 X, 큐는 함수 내에서 선언해도 됨 (전역으로 사용X)
size = 2
loc_x, loc_y = 0, 0
# 처음 상어의 위치 찾기, 그 위치에 아무것도 없다고 처리(0으로 표기)
for i in range(N):
for j in range(N):
if graph[i][j] == 9:
loc_x = i
loc_y = j
graph[loc_x][loc_y] = 0
# bfs 상하좌우 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 모든 위치까지의 '최단거리'만을 계산하는 bfs 함수
def bfs():
# dist 배열에 최단 거리 계산 : 값이 -1이면 도달할 수 없다는 뜻, -1로 초기화
dist= [[-1] * N for _ in range(N)]
# 시작 위치는 도달이 가능하다고 보고, 거리는 0으로 설정
q = deque([(loc_x, loc_y)])
dist[loc_x][loc_y] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and nx < N and ny >=0 and ny < N: # 범위 확인
# 자신의 크기보다 작거나 같은 경우에만 지나갈 수 있음. 방문되지 않은 경우에만 진행
if dist[nx][ny] == -1 and graph[nx][ny] <= size:
dist[nx][ny] = dist[x][y] + 1
q.append((nx, ny))
# 모든 위치까지의 최단 거리 테이블 반환
return dist
# 최단 거리 테이블이 주어졌을 때, 먹을 물고기를 찾는 함수
def find(dist):
x, y = 0, 0
min_dist = INF
for i in range(N):
for j in range(N):
# 도달 가능하고 먹을 수 있는 물고기일 때
if dist[i][j] != -1 and graph[i][j] >= 1 and graph[i][j] < size:
# 가장 가까운 물고기 한마리만 선택
if dist[i][j] < min_dist:
x, y = i, j
min_dist = dist[i][j]
if min_dist == INF: # 먹을 수 있는 물고기가 없는 경우
return None
else:
return x, y, min_dist # 먹을 물고기의 위치와 최단 거리 리턴
time = 0 # 출력물
ate = 0 # 현재 크기에서 먹은 양
while True:
# 먹을 수 있는 물고기의 위치 찾기
value = find(bfs())
# 먹을 수 있는 물고기가 없는 경우, 현재까지 움직인 거리(시간) 출력
if value == None:
print(time)
break
else:
# 현재 상어 위치 갱신 및 이동거리 변경
loc_x, loc_y = value[0], value[1]
time += value[2]
# 먹은 위치에는 이제 아무것도 없도록 0으로 처리
graph[loc_x][loc_y] = 0
ate += 1
# 자신의 현재 크기 이상으로 먹은 경우, 크기 증가
if ate >= size:
size += 1
ate = 0Comment
-
시간은 정말 오래걸렸지만 스스로 분석하고 풀이에 성공한 문제이다.
처음에 시간초과가 떠서 어느 부분에서 시간을 줄여야 되는지 고민을 많이 했는데, 역시 처음부터 고민했던 부분이 쓸모없는 부분이었다. (아이디어에 적은 것) 그 부분을 해결하니 바로 정답처리 ㅎ.ㅎ -
이코테 풀이랑 흐름이 너무 유사해서 놀랐다.
실력이 늘고 있는 것인가.. 아니면 모든 이들의 사고가 비슷한 것일까(?)
물론 이코테 풀이에서 배운 부분이 너무 많다.1️⃣ 함수 인자 전달 활용 / 전역변수 최소화 나는 전역변수로 때려박았는데 이코테 풀이는 야무지게 인자로 주고받으며 활용한다. 특히 비용(cost 또는 dist)을 표시하는 이차원배열 주고받기 그리고 파이썬 함수에서 하나 이상의 인자를 반환할 수 있음은 알았지만, 여러개를 반환했을 때 배열 꼴이 되는 것은 몰랐다. 좋은 배움 +1 또한 deque는 전역으로 선언하지 않고, bfs 내에서만 필요하므로 지역변수로 활용하면 된다. 2️⃣ 컴팩트한 조건 나는 '구현', '정답 처리'에만 목이 매어 생각한 모든 조건들을 때려박은 반면, 이코테 풀이는 딱 필요한 조건만 들어간 느낌이다. 특히 상어의 위치를 나처럼 굳이 그래프에서 9로 바꾸어주며 표시할 필요 없이 그냥 0으로 처리해도 되는.. 그리고 최단 경로 찾는 bfs함수에서도 방문하지 않은 경우 무조건 값을 갱신하는 건데 나처럼 굳이 비교문을 작성한다는둥..
맨 아래가 시간초과 났을 때, 아래서 두번째가 시간초과 해결, 세번째는.. 이코테 코드로 얼마나 개선됐는지 제출했는데 한줄 없어서 틀린 거고(제발..) 마지막은 이코테 코드로 제출했을 때이다.
시간이 꽤 단축됐는데.. 이유는 잘 모르겠다. (?)
혹시 이 글을 열심히 읽으신 분이 계시고.. 이유를 아시는 분이 계시다면 댓글 부탁드립니다..
아무튼 해결완!
My Precious Records