청소년 상어
문제 링크
https://www.acmicpc.net/problem/19236
풀이 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
from copy import deepcopy
import sys
sys.stdin = open('input.txt','r')
old_board = [[int(x) for x in input().split()] for _ in range(4)]
board = [[(0,0) for _ in range(4)] for _ in range(4)]
for i in range(4):
for j in range(4):
board[i][j] = (old_board[i][2*j],old_board[i][2*j+1])
# board = (물고기 번호, 물고기의 방향)
dir = [(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1)] #↑, ↖, ←, ↙, ↓, ↘, →, ↗
# 상어는 (0,0) 부터 항상 시작
# 물고기를 먹고 (0,0) 자리에 들어간다
# 그리고 (0,0)의 물고기의 방향을 갖게된다
shark_position = (0,0)
shark_size,shark_dir = board[0][0]
board[0][0] = ('Shark',shark_size,shark_dir)
# 물고기의 이동!
# 물고기가 이동할 수 있는 경우는 다른 물고기가 있고, 상어가 없을경우
# 이동할 수 있을때까지 반시계 방향으로 45도 회전
def fish_move(board):
num = 1
while num < 17:
flag = 0
for i in range(4):
for j in range(4):
# 'Shark' 가 아니고 num과 board[i][j][0] 가 찾으려는 물고기 번호와 같을경우
if type(board[i][j][0]) == int and board[i][j][0] == num:
fish_dir = board[i][j][1]-1
while True: # 물고기가 이동할 수 있을 떄 까지 방향 계속 45도 반시계 회전
dx,dy = dir[fish_dir]
# 상어가 없고 물고기가 있는 자리이며 범위 안에들어올경우
if -1 < i+dx < 4 and -1 < j+dy <4 and board[i+dx][j+dy][0] != 'Shark' and board[i+dx][j+dy] != 0:
board[i][j], board[i+dx][j+dy] = board[i+dx][j+dy],board[i][j]
flag = 1
break
else:
fish_dir = (fish_dir + 1)%8
board[i][j] = (board[i][j][0],fish_dir+1)
if flag == 1:
break
if flag == 1:
break
num += 1
return board
board = fish_move(board)
# print(board)
# 물고기가 모두 이동했으니 이제 상어가 이동할 순서이다.
# 상어가 이동 할 수 있는 좌표 후보군들 찾기
stack = []
def shark_stack(stack, shark_size, shark_dir, shark_position, board):
x, y = shark_position
for k in range(1,4):
new_board = deepcopy(board)
dx,dy = dir[shark_dir-1]
dx *= k
dy *= k
if -1 < x+dx < 4 and -1 < y+dy < 4 and board[x+dx][y+dy][0] != 0: # 범위안에 들어가고 물고기가 있는 자리
new_shark_size = shark_size + new_board[x+dx][y+dy][0]
new_shark_dir = new_board[x+dx][y+dy][1]
new_board[x+dx][y+dy] = ('Shark',new_shark_size,new_shark_dir)
new_shark_position = (x+dx,y+dy)
new_board[x][y] = (0,0)
stack.append([new_shark_size, new_shark_dir, new_shark_position, new_board])
return stack
stack = shark_stack(stack, shark_size, shark_dir, shark_position, board)
# print(stack)
max_fish_size = 0
while stack:
shark_size, shark_dir, shark_position, board = stack.pop()
if shark_size > max_fish_size:
max_fish_size = shark_size
# 물고기 이동
board = fish_move(board)
stack = shark_stack(stack, shark_size, shark_dir, shark_position, board)
print(max_fish_size)
풀이 방법
전체적인 흐름은 일단 물고기가 이동하는 fish_move() 함수와 상어가 이동 가능한 자리 후보들을 찾는 shark_stack 함수를 만든다.
fish_move 함수의 경우 반복문을 굉장히 많이 사용했는데 가장 작은 num의 물고기 즉, 1번 부터 시작해서 16번까지의 물고기 번호를 찾는데 이를 num = 1 로 초기화 한 후에 16까지 되었을때 break 되는 while 문을 사용하였다. 그리고 board 내에서 찾으려는 물고기 num는 이중 포문을 사용해서 계속 찾는 방식으로 구현하였다. 그리고 찾았을 경우는 flag 를 사용해서 for 문을 깨고 나오도록 코스트를 줄였다. 그리고 해당 번호(num)을 찾았지만 물고기가 이동할 수 없는 경우 ( 상어가 있는자리, 물고기가 있는 자리)
45도 반시계 방향 회전은 문제에서 주어진대로 했을경우 인덱스 1씩 증가시 45도 반시계 방향 회전이 된다. 따라서 fish_dir = (fish_dir + 1)%8 로 해줄 경우 문제에서 요구하는 바를 해결할 수 있음
1
2
3
else:
fish_dir = (fish_dir + 1)%8
board[i][j] = (board[i][j][0],fish_dir+1)
그리고 이제 shark_stack 함수
이 함수의 경우는 dfs 를 사용하였고, 완탐으로 풀었다. 상어가 움직일 수 있는 자리를 모두 찾고 deepcopy 를 이용해서 새로운 board를 stack에 append 하면서 하나씩 추가하는 방식으로 구현하였다. 그리고 상어가 이동할 수 있는 자리는 최대 3번 증가이기 때문에 for k in range(1,4): 에서 dx *= k , dy *= k 로 후보군들을 찾았다..
이렇게 각각의 함수를 만든 뒤 초기에 상어를 [0,0]에 위치시키고 잡아먹었으니 물고기를 이동해주고 while문을 통해 stack이 빈값이 될때까지 (dfs) 돌려줬다. 그리고 max_fish_size 를 0으로 초기화 한 뒤 stack.pop() 시 나오는 상어의 크기와 앞의 값을 비교해서 최대값을 할당해 주는 방식으로 진행하였다.
결국 이문제는 완전탐색과 dfs 로 풀이하였고, 이 문제의 핵심은 물고기의 방향을 45도 반시계 방향으로 회전하는 것, 그리고 stack에 어떠한 값들을 할당할 것인지에 대해 고민하는 것이 중요한 것 같다.
확인해야할 점
일단 입력 받는것을 처음에 애먹었다. board[ i ] [ j ]= (물고기 번호, 물고기의 방향) 를 4*4 배열로 입력받는데 잘 몰라서 결국 한번 입력받은다음에 걔네를 쪼개서 board = (물고기 번호, 물고기의 방향) 처럼 만들었다. . 이것은 다른 사람의 더 깔끔한 코드가 있으면 참고해야 할 것이다.