이거 풀다가 진짜 정신나가는 줄 알았다
문제
금방이라도 정신 가출할 것 같은 정신 사나운 화살표 배열에서 알 수 있듯이 이 문제는 2차원 배열을 돌려놨다가 다시 제자리로 돌리면서 동시에 탐색까지 수행해야하는 2차원 배열을 사용한 재귀 문제다
막상 풀고나면 어렵진 않은데 재귀 때문에 그래프가 어떤 꼴로 돌아가는지 도저히 짐작이 안 가서 디버깅하다가 죽을 뻔한 썰 푼다
아 근데 재귀로 안 풀어도 풀리긴 할 텐데 그게 더 복잡할 것 같아서 생각 안 해봄...
풀이
닭이 먼저냐 달걀이 먼저냐는 알 수 없지만 상어가 먼저냐 물고기가 먼저냐는 알 수 있다. 이런 구현 문제를 풀 때는 순서가 중요하다. 뭐가 먼저 움직였는지, 뭐가 움직인 다음에 무슨 일이 일어났는지 순서를 파악하고 그대로 구현하지 않으면 엄청난 지옥을 맛볼 수 있다.
아무튼 이 문제는 1. 상어가 움직이고 >> 2. 물고기가 움직인다 이것만 알면 절반은 풀었다. 상어가 움직이는 함수, 물고기가 움직이는 함수를 짠 다음에 순서대로 재귀에 넣어주면 끝!
상어는 물고기의 방향을 잡아먹지만 물고기끼리는 그냥 서로 위치만 바뀌기 때문에 물고기의 값이 저장된 배열과 방향 데이터가 저장된 배열을 따로 받아서 저장했다.
- 상어가 움직인다. 상어는 (0, 0)에 있는 물고기부터 먹는다.
- 물고기가 움직인다.
- 작은 번호의 물고기부터 움직인다.
- 주어진 방향에 물고기가 있거나, 빈 칸이면 이동한다
- 하지만 주어진 방향에 상어가 있거나 갈 수 없는 칸이면 반시계 방향으로 회전한 방향을 탐색한다
- 물고기가 이동할 수 있는 방향을 찾으면 그 방향으로 이동하고 그 방향으로 물고기가 가지고 있는 방향 데이터를 업데이트 해준다.
- 물고기가 이동하면 상어가 움직인다
- 상어는 자신이 방금 먹은 물고기의 방향을 가지게 된다. 그 방향으로만 끝까지 이동할 수 있으며 한 번에 한 마리의 물고기만 먹을 수 있다.
- 가는 길에 여러 마리를 먹는 건 안 된다
- 상어는 물고기가 있는 칸으로만 움직일 수 있지만 가는 길에 물고기가 없다고 해서 그 너머에 있는 물고기를 못 먹는 건 아니다.
- (상어) 0 1 7 이렇게 되어 있다면 0 은 건너뛰고 1, 7 물고기를 먹으면 된다
- 재귀로 이 문제를 접근하게 된다면 물고기가 이동하면서 2차원 배열의 값이 계속 변경되기 때문에 deepcopy나 슬라이싱을 통해 배열을 복사해서 기존 배열 값이 변경되지 않은 채로 있을 수 있도록 처리해야 함
여기서 2번에 있는 물고기의 방향 업데이트 부분을 파악 못해서 일생 일대의 실수를 저질러 버렸다
일생 일대의 실수
-
처음엔 단순하게 물고기가 움직인 다음에 상어가 먹고 나서 다시 돌아오면 물고기를 원래대로 돌리는 revert() 함수를 짜려고 했다... 이는 아주 잘못된 생각이었다...
-
왜냐하면, 물고기는 자신이 이동할 수 있는 방향을 찾게 되면 기존에 자기가 갖고 있던 방향을 새로운 방향값으로 업데이트해준다. 즉, 우리는 기존에 물고기가 뭔 방향을 갖고 있었는지, 이게 새로운 방향인지 아닌지를 알 수가 없다.
-
근데 이 revert() 함수는 물고기의 값을 업데이트 하지 않은 상태에서, 180도 반대 방향에서부터 반시계 방향으로 돌면서 갈 수 있는 방향을 찾는 건데, 이렇게하면 되돌아올 수 있을 줄 알았다.
그럴 수 없었다
- 아래의 코드를 가지고 아무리 되돌려도 원래의 배열로 복구되지 않는 게 이상해서 구글링을 통해 몇몇 코드를 참고하다가 바로 저 값 업데이트 부분을 찾게 된 것이다... 이래서 문제를 똑바로 봐야 한다. 문제에 제대로 설명이 되어 있는 것 같진 않은데 그림을 자세히 보다보면 물고기의 방향도 계속 변경되는 게 나온다. ㅎㅎ..
def revert():
for n in range(16, 0, -1):
if not loc.get(n):
continue
x, y = loc[n]
d = (dir[x][y]+4)%8
for k in range(8):
nx, ny = x+dx[(d+k)%8], y+dy[(d+k)%8]
if n == 13:
print(nx, ny, d)
if nx<0 or ny<0 or nx>3 or ny>3 or fish[nx][ny] == -1:
continue
print(n, nx, ny)
if (_n:=fish[nx][ny])>0:
loc[n], loc[_n] = loc[_n], loc[n]
else:
loc[n] = [nx, ny]
fish[nx][ny], fish[x][y] = fish[x][y], fish[nx][ny]
dir[nx][ny], dir[x][y] = dir[x][y], dir[nx][ny]
break
_print()물고기의 이동
-
작은 숫자의 물고기부터 이동한다
-
물고기가 이동한 방향으로 방향 데이터를 업데이트 해주는 부분만 고려해주면 크게 어렵지 않음
def move(fish, dir, loc): for n in range(1, 17): if not loc.get(n): continue x, y = loc[n] d = dir[x][y] while 1: nx, ny = x+dx[d], y+dy[d] if nx<0 or ny<0 or nx>3 or ny>3 or fish[nx][ny] == -1: d = (d+1)%8 continue if (_n:=fish[nx][ny])>0: loc[n], loc[_n] = loc[_n], loc[n] else: loc[n] = [nx, ny] dir[x][y] = d # 물고기가 갖고 있는 방향 업데이트 fish[nx][ny], fish[x][y] = fish[x][y], fish[nx][ny] dir[nx][ny], dir[x][y] = dir[x][y], dir[nx][ny] break
상어의 이동
- 상어가 물고기를 먹고 현재 위치한 부분은 -1 처리를 해준다
- 상어는 기본적으로 방금 먹은 물고기의 방향 데이터를 가진다
- 상어가 이동할 수 있는 방향으로 계속 이동하는데 더 갈 수 있는데가 없으면 끝이다. 단, 그냥 물고기가 없는 칸은 건너 뛰는 처리를 해야 한다.
- 상어가 먹은 물고기는 다음 번 물고기 이동에서 방향을 바꾸면 안 되기 때문에 물고기의 2차원 배열 위치 데이터가 저장된 loc 딕셔너리에서 값을 삭제해야 한다.
- 갈 수 있는 곳이 한 군데도 없으면 집에 돌아간다 = 종료된다 고 했으므로 갈 수 있는 곳이 단 한 군데도 없는 cnt = 0 값이 나오게 되면 그때 먹은 물고기의 최대 값을 비교하고 return 한다
- 재귀이기 때문에 상어가 1번 물고기를 먹었을 때 물고기가 회전한 후, 다시 7번 물고기를 먹으러 가기 전에는 1번 물고기 먹고 물고기 회전하기 이전의 배열 값을 가지고 있어야 한다. 즉 모든 물고기 관련 데이터들의 값을 다 복사해둬야 한다. 여기서 deepcopy를 쓰면 깔끔하게 해결될 거 같지만 딱 봐도 오래걸릴 거 같아서 다른 블로그를 참고해서 각 행마다 슬라이싱 복사하는 방식을 사용했다.
def eat(sx, sy, total_eat, fish, dir, loc): # 현재 상어의 위치
global ans
fish[sx][sy] = -1
d = dir[sx][sy]
# 물고기 움직이기
move(fish, dir, loc)
fish[sx][sy] = 0
cnt = 0
while 1:
nx, ny = sx+dx[d], sy+dy[d]
# 더 이상 갈 수 있는 데가 없음
if nx<0 or ny<0 or nx>3 or ny>3:
break
if fish[nx][ny] == 0:
# 물고기가 없으면 그냥 못 감
sx, sy = nx, ny
continue
# 상어가 잡아먹게 될 물고기의 번호
f = fish[nx][ny]
# 상어가 먹어서 물고기의 위치 딕셔너리에는 없어져야 하기 때문에 삭제
tmp_loc = copy_dict(loc)
del loc[f]
# 현재의 물고기 배열 상태를 카피 해둔 다음에 이동 -> 이동하게 되면 물고기가 이동하는 move() 함수가 작동
tmp_fish = [row[:] for row in fish]
tmp_dir = [row[:] for row in dir]
eat(nx, ny, total_eat+f, tmp_fish, tmp_dir, loc)
# 물고기의 위치와 방향담은 배열도 원상복귀
# fish = [row[:] for row in tmp_fish]
# dir = [row[:] for row in tmp_dir]
# 물고기의 위치 원상복귀
loc = copy_dict(tmp_loc)
fish[nx][ny] = f
# 갈 수 있는 곳이 있었기 때문에 cnt += 1
cnt += 1
sx, sy = nx, ny
if not cnt:
# 먹을 수 있는 물고기가 하나도 없었거나... 이동할 수 있는 방향이 하나도 없었다면 값 비교
ans = max(ans, total_eat)
return 최종 코드
- loc: 물고기의 번호를 키값, 2차원 배열의 위치값를 value 값으로 가지는 딕셔너리
- fish : 2차원 배열 물고기의 번호를 갖고 있음
- dir : 2차원 배열 물고기의 방향을 갖고 있음
# 44ms
def copy_dict(dic):
new_dict = {}
for k, v in dic.items():
new_dict[k] = v
return new_dict
# 청소년 상어
def move(fish, dir, loc):
for n in range(1, 17):
if not loc.get(n):
continue
x, y = loc[n]
d = dir[x][y]
while 1:
nx, ny = x+dx[d], y+dy[d]
if nx<0 or ny<0 or nx>3 or ny>3 or fish[nx][ny] == -1:
d = (d+1)%8
continue
if (_n:=fish[nx][ny])>0:
loc[n], loc[_n] = loc[_n], loc[n]
else:
loc[n] = [nx, ny]
dir[x][y] = d # 물고기가 갖고 있는 방향 업데이트
fish[nx][ny], fish[x][y] = fish[x][y], fish[nx][ny]
dir[nx][ny], dir[x][y] = dir[x][y], dir[nx][ny]
break
def eat(sx, sy, total_eat, fish, dir, loc): # 현재 상어의 위치
global ans
fish[sx][sy] = -1
d = dir[sx][sy]
# 물고기 움직이기
move(fish, dir, loc)
fish[sx][sy] = 0
cnt = 0
while 1:
nx, ny = sx+dx[d], sy+dy[d]
# 더 이상 갈 수 있는 데가 없음
if nx<0 or ny<0 or nx>3 or ny>3:
break
if fish[nx][ny] == 0:
# 물고기가 없으면 그냥 못 감
sx, sy = nx, ny
continue
# 상어가 잡아먹게 될 물고기의 번호
f = fish[nx][ny]
# 상어가 먹어서 물고기의 위치 딕셔너리에는 없어져야 하기 때문에 삭제
tmp_loc = copy_dict(loc)
del loc[f]
# 현재의 물고기 배열 상태를 카피 해둔 다음에 이동 -> 이동하게 되면 물고기가 이동하는 move() 함수가 작동
tmp_fish = [row[:] for row in fish]
tmp_dir = [row[:] for row in dir]
eat(nx, ny, total_eat+f, tmp_fish, tmp_dir, loc)
# 물고기의 위치와 방향담은 배열도 원상복귀
# fish = [row[:] for row in tmp_fish]
# dir = [row[:] for row in tmp_dir]
# 물고기의 위치 원상복귀
loc = copy_dict(tmp_loc)
fish[nx][ny] = f
# 갈 수 있는 곳이 있었기 때문에 cnt += 1
cnt += 1
sx, sy = nx, ny
if not cnt:
# 먹을 수 있는 물고기가 하나도 없었거나... 이동할 수 있는 방향이 하나도 없었다면 값 비교
ans = max(ans, total_eat)
return
# 입력받기
dx = (-1, -1, 0, 1, 1, 1, 0, -1)
dy = (0, -1, -1, -1, 0, 1, 1, 1)
loc = {} # 물고기의 번호에 따른 배열의 위치
fish = [[0]*4 for _ in range(4)] # 물고기의 번호가 담긴 배열
dir = [[0]*4 for _ in range(4)] # 물고기의 이동방향이 담긴 배열
ans = 0
for i in range(4):
row = list(map(int, input().split()))
for j in range(4):
n, d = row[2*j:2*j+2]
loc[n] = [i, j]
fish[i][j], dir[i][j] = n, d-1
del loc[fish[0][0]]
eat(0, 0, fish[0][0], fish, dir, loc)
print(ans)
후기
문제의 순서를 짜는 건 어렵지 않았는데 재귀랑 배열 복사를 간과해서 배열이랑 딕셔너리가 계속 변경되고 변경된 상태로 또 재귀함수를 수행하면서 디버깅이 굉장히 복잡해졌다. 그 부분만 처음부터 잘 고려하고 설계했다면 크게 어렵지 않았을 수도 있었을 거 같다.
아무말이나하기