https://www.acmicpc.net/problem/19236
문제 아기 상어가 성장해 청소년 상어가 되었다. ([그래프/시뮬레이션] 아기상어 백준 16236번)
4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.
오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.
물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.
물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.
<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.
이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.
2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.
3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.
물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.
위 설명을 천천히 따라가면 되지만 다시 간단하게 정리를 해보면
시작은 테이블은 각 물고기와 방향을 설정을 합니다. 그리고 상어는 0,0에 들어갑니다.
모든 물고기는 번호가 낮은 것부터 이동을 시작하고 이동하는 곳이 범위 밖이거나 상어가 있다면 45도 회전을 하고 이동을 합니다.
모든 물고기가 이동을 했다면 상어가 이동을 합니다. 이때 상어의 위치와 방향은 0,0에 있던 물고기 입니다. 그리고 이동할 수 있는 방향에 물고기가 있다면 먹으로 갑니다. 그리고 마찬가지로 먹은 물고기의 방향을 가지게 됩니다.
모든 과정이 더이사 이동할 수 없을때까지 반복을 합니다. 먹은 물고기의 최대값은 얼마인가요?
여러가지 조건을 걸어두었고 해당 조건을 착실하게 만족을 하면 되겠네요 이때 자연스럽게 하나의 함수로는 안되고 여러 함수를 쪼개야 겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import copy
# 4x4 크기의 정사각형에 존재하는 각 물고기의 번호(없으면 - 1)와 방향 값을 담는 테이블
array = [[None]*4 for _ in range(4)]
for i in range(4):
data = list(map(int, input().split()))
#매 줄마다 4마리의 물고기를 하나씩 확인하며
for j in range(4):
#각 위치마다 물고기의 번호, 방향을 저장
array[i][j] = [data[j*2], data[j * 2 + 1] - 1]
#8가지 방향에 대한 정의
dx = [-1,-1,0,1,1,1,0,-1]
dy = [0,-1,-1,-1,0,1,1,1]
#현재 위치에서 왼쪽으로 회전된 결과 반환
def turn_left(direction):
return (direction + 1)%8
result = 0 #최종 결과
데이터를 입력을 받을때 테이블의 크기 자체는 4x4로 고정이 되어 있지만 방향값도 들어오기 때문에 한줄당 8개를 받게 됩니다. 그러니 물고기 번호는 인덱스가 0, 2, 4, 6, … 이런식으로 0에서 2씩 더해지는 순서이고 방향의 인덱스는 1,3,5,… 가 됩니다. 그런데 방향은 1부터 8까지를 가지게 되는데 이번에도 역시 인덱스는 0부터 시작하니 이점을 유의해서 1을 빼고 시작을 합니다.
dx와 dy는 사전에 정의된 순서대로 위로 올라가는것부터 해서 쭉 정의를 합니다.(x는 row이고 y는 column입니다. 그러니 한줄이 올라가는 것은 x가 하나 빠지는 것입니다)
방향은 1씩 증가를 하는데 1부터 7까지 입니다. 이는 다르게 말하면 8의 나머지가 되는 것이고 방향은 %8를 이용합니다. 이런 순서가 증가하는데 특정 구간의 숫자가 반복될 경우 나머지 연산을 사용합니다.
1
2
3
4
5
6
7
#현재 배열에서 특정한 번호의 물고기 위치 찾기
def find_fish(array, index):
for i in range(4):
for j in range(4):
if array[i][j][0] == index:
return (i,j)
return None
특정 번호의 물고기를 찾는 함수 입니다. 물고기 번호는 1번부터 16번까지 고정되어 있는데 어디에 몇번 물고기가 있는지는 위 함수를 통해서 찾을 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#모든 물고기를 회전 및 이동시키는 함수
def move_all_fishes(array, now_x, now_y):
#1번부터 16번까지의 물고기를 차례대로 (낮은번호대로) 확인
for i in range(1,17):
#해당 물고기의 위치 찾기
position = find_fish(array,i)
if position != None:
x,y = position[0], position[1]
direction = array[x][y][1]
#해당 물고기의 방향을 왼쪽으로 계속 회전시키며 이동이 가능한지 확인
for j in range(8):
nx = x + dx[direction]
ny = y + dy[direction]
#해당 방향으로 이동이 가능하다면 이동시키기
if 0 <= nx and nx < 4 and 0 <= ny and ny < 4:
if not(nx==now_x and ny == now_y):
array[x][y][1] = direction
array[x][y], array[nx][ny] = array[nx][ny], array[x][y]
break
direction = turn_left(direction)
모든 물고기는 이동을 하게 되는데 이때 사용할 함수 입니다. 1번부터 16번 물고기까지 찾게 됩니다.
물고기의 번호를 순서대로 찾습니다. 그리고 물고기가 존재를 하고 방향을 확인하면서 이동이 가능한지 체크를 하고 이동이 가능하다면 물고기의 위치를 변경하고 for문을 빠져나오고 아니라면 계속해서 물고기를 돌립니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#상어가 현재 위치에서 먹을 수 있는 모든 물고기의 위치 반환
def get_possible_positions(array, now_x, now_y):
positions = []
direction = array[now_x][now_y][1]
#현재의 방향으로 계속 이동하기
for i in range(4):
now_x += dx[direction]
now_y += dy[direction]
#범위를 벗어나지 않는지 확인하며
if 0 <= now_x and now_x < 4 and 0 <= now_y and now_y < 4:
#물고기가 존재하는 경우
if array[now_x][now_y][0] != -1:
positions.append((now_x, now_y))
return positions
현재 위치에서 물고기를 먹을 수 있는지 확인을 합니다. 물고기의 방향을 확인을 하고 범위를 벗어나지 않는지 확인을 하고 물고기가 존재하는 경우를 확인합니다. 이때 갈 수 있는 최대 길이를 확인하게 끝까지 가보게 됩니다.
그러면 positions에는 갈 수 있는 곳이 차례대로 들어갑니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#모든 경우를 탐색하기 위한 DFS함수
def dfs(array, now_x, now_y, total):
global result
array = copy.deepcopy(array) #리소스를 통째로 복사
total += array[now_x][now_y][0] #현재 위치의 물고기 먹기
array[now_x][now_y][0] = -1 #물고기를 먹었으므로 번호 값을 -1로 변환
move_all_fishes(array, now_x, now_y) #전체 물고기 이동시키기
#이제 다시 상어가 이동할 차례이므로, 이동 가능한 위치 찾기
positions = get_possible_positions(array, now_x, now_y)
#이동할 수 있는 위치가 하나도 없다면 종료
if len(positions) == 0:
result = max(result, total) #최댓값 지정
return
#모든 이동할 수 있는 위치로 재귀적으로 수행
for next_x, next_y in positions:
dfs(array, next_x, next_y, total)
#청소년 상어의 시작위치(0,0)에서부터 재귀적으로 모든 경우 탐색
dfs(array, 0,0,0)
print(result)
이제 위에서 만든 함수를 가지고 재귀적으로 탐색을 하게 됩니다.
지금까지 만든 함수는
물고기를 회전시키기
특정 위치의 물고기를 찾기
모든 물고기를 회전과 이동 시키는 함수
상어가 현재 먹을 수 있는 물고기 위치를 반환
일단 현재 위치의 물고기를 먹는 것으로 시작합니다. 당연히 먹었으니 total에 추가를 합니다. 그리고 상어가 이동 할 수 있는 곳은 물고기가 존재하는 곳만 가능하니 먹은 곳에 대해서는 -1이라고 해줍시다.
이제 모든 물고기를 이동을 시켜줍니다. 그리고 상어가 이동할 차례이므로 이동 가능한 위치를 찾고 positions에는 여러가지 변수가 기록이 됩니다. 이를 순서대로 탐색을 쭉 진행을합니다. 마지막으로 더 이상 이동할 곳이 없을때까지 진행합니다.
Comments powered by Disqus.