최근 SW 역량 테스트 때문에 알고리즘 문제 풀이에 집중하고 있어서.. 블로그를 등한시 하고 있습니다.. 죄송합니다!! 그래서 오늘은 제가 풀고 있는 알고리즘 풀이를 해보려고 합니다.
아기, 청소년, 어른 상어에 이에 마법사 상어 시리즈의 마지막 단계인 마법사 상어와 복제입니다.
나머지 마법사 상어 시리즈 문제도 모두 풀어보긴 했지만, 이 문제가 가장 화가 많이 나더군요.. 될듯 하면서 안 되는 그런.. 여튼
이 문제는 문제에서 요구하는 것을 그대로 구현하면 풀리는 문제였습니다. 단지 제가 아직 Python에 대한 특성을 잘 알고 있지 않거나, 애매한 오타로 인해 풀이가 좀 오래걸렸을 뿐입니다...하하...
코드를 하나씩 보면서 해설 들어가보죠!
from copy import deepcopy
import sys
from itertools import product
input = sys.stdin.readline
m, s = map(int, input().split())
bowl = [[[] for _ in range(4)] for _ in range(4)]
smell = [[0 for _ in range(4)] for _ in range(4)]
shark_move = list(product(range(4), range(4), range(4)))
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
s_dx = [-1, 0, 1, 0]
s_dy = [0, -1, 0, 1]
for _ in range(m):
x, y, d = map(int, input().split())
bowl[x-1][y-1].append(d-1)
sx, sy = map(int, input().split())
sx -= 1
sy -= 1문제를 풀기 전에 설계를 진행하는 곳입니다.
저는 shark_move라는 것을 따로 만들었어요. 문제 설명 최하단에 64가지 경로로 진행할 수 있다고 이야기 했었기 때문에, 이를 갖고 있다가 필요할 때 순회하면 되겠다 생각하고 있었습니다. 어차피 삼성 SW 역량테스트는 구현이 대부분이기 때문에, 웬만하면 시간복잡도가 통과되기도 하고
문제의 조건상 복제는 최대 100번, 물고기도 초반에 최대 10마리, 4by4 행렬에서 알고리즘이 진행되기 때문에, 16 ✖️ 100 ✖️ 10 정도로 문제 제한 시간인 2초를 넘기지 않는 것을 느낄 수 있습니다.
dx,dy는 물고기 이동 경로이고, s_dx, s_dy는 상어 이동경로 입니다. 각각 문제의 조건에 따라 알맞은 index로 넣어줬습니다. (마법사 상어 시리즈는 다 이렇습니다..)
bowl은 물고기가 이동할 때 사용할 배열이구요.
smell은 냄새가 있는지 기록할 배열입니다.
bowl에 원소를 담을 때, 방향만 담았습니다. 굳이 위치까지 저장할 필요는 없었습니다. 왜냐하면, bowl의 index가 알려주기 때문이죠.
물고기 복제
# TODO 물고기 복제
bowl_copy = deepcopy(bowl)
bowl_move = [[[] for _ in range(4)] for _ in range(4)]bowl_move는 bowl에서 물고기가 이동한 이후에 방향을 담을 배열입니다.
물고기 이동
# TODO 물고기 이동
for i in range(4):
for j in range(4):
while bowl[i][j]:
fd = bowl[i][j].pop()
for _ in range(8):
nx, ny = i + dx[fd], j + dy[fd]
if not (0 <= nx < 4 and 0 <= ny < 4):
fd = (fd + 7) % 8
continue
if smell[nx][ny] > 0 or (nx == sx and ny == sy):
fd = (fd + 7) % 8
continue
bowl_move[nx][ny].append(fd)
break
else:
bowl_move[i][j].append(fd)여기서 얻어 갈 것은 사실 문제에서 요구한 반시계 방향을 코드로 어떻게 짤것인가? 인데, 방향을 -1씩 감소시키면 큰일나니(0보다 작게되면...), 반대로 7씩 더해서 8로 나눴습니다. 그리고 이동 가능하다면 원소를 bowl_move에 추가시키고 break을 걸어줍니다. 만약에 이 break을 거치지 않았다면, 이동할수가 없다는 의미이므로, 원래 위치에 방향을 넣어줍니다.
상어 이동 경로 파악
# TODO 상어 이동 경로 파악
shark_routes = []
for s_m in shark_move:
route_value = set()
flag = 0
x, y = sx, sy
for d in s_m:
nx, ny = x + s_dx[d], y + s_dy[d]
if not (0 <= nx < 4 and 0 <= ny < 4):
flag = 1
break
route_value.add((nx, ny))
x, y = nx, ny
if flag: continue
num = 0
for x, y in route_value:
num += len(bowl_move[x][y])
shark_routes.append(list(s_m) + [num])
shark_routes.sort(key=lambda x: [-x[3], x[0], x[1], x[2]])
route = shark_routes[0]사실 이부분이 제일 빡셌습니다. 문제를 풀다보니, 상어가 왔던 경로를 다시 타서 돌아오면, 중복해서 물고기 개수를 세어버려서 문제에서 요구한 경로가 나타나질 않았습니다. 그래서 route_value을 set으로 만든 뒤에 해당 좌표를 tuple값으로 저장해버렸습니다. 중복된 경로의 경우 다시는 물고기를 계산하지 않기 위해서입니다. 이러한 route_value가 모이면, 이를 활용하여 각 index에 위치한 물고기 수를 한번 씩만 더해준 후 경로와 계산된 물고기 수 모두를 shark_route에 담습니다. 그리고 물고기 수, 경로 숫자별로 sort해줍니다.
여기서 가장 처음에 나온 원소가 바로 문제에서 요구했던, 경로인거죠.
상어 경로를 알았다면, 사실 그 이후의 구현은 매우 쉬워집니다.
나머지 구현
# TODO 상어 이동
for i in range(3):
nx, ny = sx + s_dx[route[i]], sy + s_dy[route[i]]
if bowl_move[nx][ny]:
smell[nx][ny] = rounding
bowl_move[nx][ny].clear()
sx, sy = nx, ny
# TODO 냄새 없애기
for i in range(4):
for j in range(4):
if abs(smell[i][j] - rounding) == 2:
smell[i][j] = 0
# TODO 물고기 추가
for i in range(4):
for j in range(4):
while bowl_copy[i][j]:
fish = bowl_copy[i][j].pop()
bowl_move[i][j].append(fish)
bowl = deepcopy(bowl_move)네.. 이 부분은 설명할게 없습니다.
최종 코드
from copy import deepcopy
import sys
from itertools import product
input = sys.stdin.readline
m, s = map(int, input().split())
bowl = [[[] for _ in range(4)] for _ in range(4)]
smell = [[0 for _ in range(4)] for _ in range(4)]
shark_move = list(product(range(4), range(4), range(4)))
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
s_dx = [-1, 0, 1, 0]
s_dy = [0, -1, 0, 1]
for _ in range(m):
x, y, d = map(int, input().split())
bowl[x-1][y-1].append(d-1)
sx, sy = map(int, input().split())
sx -= 1
sy -= 1
for rounding in range(1, s+1):
# TODO 물고기 복제
bowl_copy = deepcopy(bowl)
bowl_move = [[[] for _ in range(4)] for _ in range(4)]
# TODO 물고기 이동
for i in range(4):
for j in range(4):
while bowl[i][j]:
fd = bowl[i][j].pop()
for _ in range(8):
nx, ny = i + dx[fd], j + dy[fd]
if not (0 <= nx < 4 and 0 <= ny < 4):
fd = (fd + 7) % 8
continue
if smell[nx][ny] > 0 or (nx == sx and ny == sy):
fd = (fd + 7) % 8
continue
bowl_move[nx][ny].append(fd)
break
else:
bowl_move[i][j].append(fd)
# TODO 상어 이동 경로 파악
shark_routes = []
for s_m in shark_move:
route_value = set()
flag = 0
x, y = sx, sy
for d in s_m:
nx, ny = x + s_dx[d], y + s_dy[d]
if not (0 <= nx < 4 and 0 <= ny < 4):
flag = 1
break
route_value.add((nx, ny))
x, y = nx, ny
if flag: continue
num = 0
for x, y in route_value:
num += len(bowl_move[x][y])
shark_routes.append(list(s_m) + [num])
shark_routes.sort(key=lambda x: [-x[3], x[0], x[1], x[2]])
route = shark_routes[0]
# TODO 상어 이동
for i in range(3):
nx, ny = sx + s_dx[route[i]], sy + s_dy[route[i]]
if bowl_move[nx][ny]:
smell[nx][ny] = rounding
bowl_move[nx][ny].clear()
sx, sy = nx, ny
# TODO 냄새 없애기
for i in range(4):
for j in range(4):
if abs(smell[i][j] - rounding) == 2:
smell[i][j] = 0
# TODO 물고기 추가
for i in range(4):
for j in range(4):
while bowl_copy[i][j]:
fish = bowl_copy[i][j].pop()
bowl_move[i][j].append(fish)
bowl = deepcopy(bowl_move)
answer = 0
for i in range(4):
for j in range(4):
answer += len(bowl[i][j])
print(answer)