19236: 청소년 상어

https://www.acmicpc.net/problem/19236

19236번: 청소년 상어

설명

우선 구하는 값은 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구하는 것이다. 문제의 조건을 잘 살펴보고 주어진 조건대로 구현하면 되는 문제이다. 

• 물고기는 번호와 방향을 갖고 있다. 1 <= 번호 <=16 이고, 두 물고기가 같은 번호를 갖는 경우는 없다. 그리고 방향은 8가지 방향(상 하 좌 우, 대각선) 중 하나를 갖는다. 1 <= 방향(d) <= 8.
• 청소년 상어는 (0,0)에 있는 물고기를 먹고 (0,0)에 들어가게 된다. 상어의 방향은 (0,0)에 있던 물고기의 방향과 같다. 그 후 물고기가 이동한다. 즉, 상어이동 후 물고기 이동한다.
• 물고기 이동은 번호가 작은 순서대로 이동한다. 물고기는 한 칸 이동가능. 이동가능 한 칸은 다른 물고기가 있는 칸 + 빈칸이다. 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 이동할 수 없다면 이동 하지 않는다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동.
• 물고기의 이동이 모두 끝나면 다시 상어가 이동한다. 한번에 여러개의 칸으로 이동할 수 있다. 
• 상어는 물고기가 있는 칸으로 이동했다면, 그 칸의 물고기를 먹고 그 물고기의 방향을 갖게 된다.
• 이동하는 중에 지나는 칸에 있는 물고기는 먹지 않는다. 
• 물고기가 없는 칸으로는 이동할 수 없다. 즉, 물고기가 있는 칸으로만 이동 가능. 이동할 수 있는 칸이 없다면 공간에서 벗어나 집으로 간다. 
• 상어 이동 후 물고기 이동. 또 다시 물고기가 이동 후 상어 이동. 이 과정을 반복하며 상어가 이동할 수 없을 때까지 반복한다.

핵심 아이디어

• 8가지 방향 고려 해야한다. 

• 구현 + DFS

1. 4*4 공간의 graph 안에 물고기가 들어있는 번호, 방향을 저장한다. 만약 물고기가 잡아먹혔을 때 번호를 0으로 바꾼다.
2. DFS를 통해 상어가 해당 방향으로 움직였을 때, 먹은 물고기 번호로 점수를 더해주고 상어가 먹은 물고기 번호 합의 최댓값을 갱신한다. 또한 상어가 이동한 지역의 물고기를 먹었으므로 해당 지역의 물고기 번호를 0으로 변경한다.
3. 상어가 물고기를 먹은 후 물고기의 움직임이 일어나는데, 물고기의 이동은 번호가 낮은 순서부터 진행되므로 해당 물고기의 번호가 존재 (먹히지 않았음)하면 해당 물고기의 방향대로 이동할 수 있다. 그러면 이동하는 곳의 위치와 현재 위치에 graph 정보를 서로 변경하고, 만약 해당 방향에 이동할 수 없다면 45도 반시계 방향으로 계속 돌면서 이동할 수 있는 곳을 찾는다. 
4. 물고기가 다 이동한 후, 상어 이동이 시작되는데 상어의 현재 방향대로 갈 수 있는 모든 곳에 이동이 가능하면 (범위를 넘지 않으면서, 물고기가 존재함) DFS로 들어가서 물고기를 먹는다.
5. 모든 DFS를 돈 후 상어가 먹은 물고기 번호의 최댓값을 출력한다.

코드 구현

# graph 만들기
graph = [[] for _ in range(4)]

for i in graph:
	print(i)
# 출력 결과 -> 아래 배열에 물고기의 정보를 담는다. [물고기번호, 방향]
[]
[]
[]
[]

# 8가지 방향
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

for i in range(4):
	data = list(map(int, input().split()))
    fish = [] # 물고기 정보를 담아서 graph에 담는다.
    for j in range(4):
    	# 물고기 번호, 방향
        # 이때 방향은 1~8이므로 -1을 해줘숴 0~7로한다.
        fish.append([data[2*j], data[2*j+1]-1])
    graph[i] = fish

for i in graph:
	print(i)
# 첫번째 예시 기준
[[7, 5], [2, 2], [15, 5], [9, 7]]
[[3, 0], [1, 7], [14, 6], [10, 0]]
[[6, 0], [13, 5], [4, 2], [11, 3]]
[[16, 0], [8, 6], [5, 1], [12, 1]]

from copy import deepcopy

# graph 입력받기
graph = [[] for _ in range(4)]
# 8가지 방향
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
for i in range(4):
	data = list(map(int, input().split()))
	fish = [] # 물고기의 번호, 방향을 담을 배열
	for j in range(4):
		# 물고기 번호, 방향
		# -1을 해주는 이유는 방향이 1~8이므로 1씩빼준다.
		fish.append([data[2*j], data[2*j+1]-1])
	graph[i] = fish

# 최종 결과 변수
max_score = 0
# dfs를 통해 상어가 해당 방향으로 움직였을 때,
# 먹을 수 있는 물고기의 번호를 다 더해주고
# 상어가 먹은 물고기의 번호의 합의 최댓값을 갱신한다.
def dfs(sx,sy,score, graph):
	global max_score
	score += graph[sx][sy][0] # 물고기 번호를 더한다.
	max_score = max(max_score, score) # 최댓값으로 갱신
	graph[sx][sy][0] = 0 # 상어가 먹은 곳은 0으로 변경

	# 물고기 움직임
	# 순서가 낮은 번호부터 움직인다.
	for f in range(1, 17):
    # 현재 물고기 좌표를 찾기 위해 초기 좌표를 유효하지 않은 값으로 설정
		fx, fy = -1,-1
		for x in range(4):
			for y in range(4):
            # 현재 위치의 물고기가 순회 중인 물고기 번호와 일치할 경우
				if graph[x][y][0] == f:
                 # 현재 물고기의 좌표를 업데이트한다.
					fx, fy = x, y
					break
        # 만약 물고기가 graph 내에 존재하지 않는 경우(초기화 값 그대로인 경우), 다음 물고기로 넘어간다.
		if fx == -1 and fy == -1:
			continue
		else:
           # 현재 물고기의 방향을 가져온다.
			fd = graph[fx][fy][1]

		# 이동할 수 있는 방향이 나올 때까지 회전
		for i in range(8):
			nd = (fd+i) % 8
			nx = fx + dx[nd]
			ny = fy + dy[nd]
			# 만약 주어진 범위를 벗어나거나 상어가 있는 칸이라면
			if not (0 <= nx < 4 and 0 <= ny < 4) or (nx == sx and ny == sy):
				continue
			else:
				graph[fx][fy][1] = nd # 아직 이동전 방향
				# 이동하려는 칸에 물고기가 있다면 서로 위치 바꾼다.
				graph[fx][fy], graph[nx][ny] = graph[nx][ny], graph[fx][fy]
				break
	# 물고기 이동후 상어가 이동하기 시작
	# 상어가 물고기 먹음
	sd = graph[sx][sy][1] # 상어의 현재 방향을 가져온다.
	for i in range(1, 5): # 상어는 최대 4칸까지 이동할 수 있다.
		# 상어는 한번에 여러 칸 이동 가능
         # 상어의 다음 위치를 계산한다. 상어의 이동 방향(sd)과 이동 가능한 칸 수(i)를 고려한다.
		nx = sx + dx[sd] * i
		ny = sy + dy[sd] * i
		# 만약 물고기를 먹고 그 물고기가 갖는 방향을 갖는다면
		# 주어진 범위에 있고 다음칸에 물고기가 있다면
		if (0 <= nx < 4) and (0 <= ny < 4) and graph[nx][ny][0] > 0:
			dfs(nx,ny,score,deepcopy(graph))

dfs(0,0,0,graph)
print(max_score)