[Python] 백준 19236. 청소년 상어

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

19236번: 청소년 상어

DFS 문제.

 

두 달 정도 쉬었더니, 그새 구현방법을 다 까먹어서 엄청 버벅댔다.

잘 만든 코드는 아니니까, 나중에 더 세련된 방법으로 다시 풀어봐야겠다...

 

 

	import sys
	from copy import deepcopy
	dirs = [(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1)]
	maps = [[0 for _ in range(4)] for _ in range(4)]
	fish_dict = dict()
	y, x = 0, 0
	for _ in range(4):
	arr = list(map(int, sys.stdin.readline().split()))
	for i in range(0, len(arr), 2):
	fish, head = arr[i], arr[i+1]-1
	maps[y][x] = [fish, head]
	fish_dict[fish] = (y, x)
	x += 1
	y += 1
	x = 0
	# 초기값. 0,0 위치
	result = 0
	def no_fish():
	return [0, None]
	def dfs(shark_pos, maps, score, fish_dict):
	global result
	# 현재 위치의 물고기 잡음
	y_s, x_s = shark_pos
	shark_heading = maps[y_s][x_s][1]
	got_fish = maps[y_s][x_s][0]
	# 잡은 물고기는 빈 공간으로
	fish_dict.pop(maps[y_s][x_s][0])
	maps[y_s][x_s] = no_fish()
	# 물고기 이동
	for f_num in range(1, 17):
	# 없는 물고기일 경우 패스
	if f_num not in fish_dict:
	continue
	y, x = fish_dict[f_num]
	# 이동할 수 없는 경우: 이동할 수 있을 때까지 확인
	can_move = False
	for _ in range(9):
	heading = dirs[maps[y][x][1]]
	ny, nx = y + heading[0], x + heading[1]
	# 공간 경계 안에 있으면서, 물고기가 이동할 수 있는 공간인 경우
	if (0 <= ny < len(maps) and 0 <= nx < len(maps[0])) and (0 <= maps[ny][nx][0] <= 16) \
	and ((ny, nx) != (y_s, x_s)):
	can_move = True
	break
	else:
	maps[y][x][1] = (maps[y][x][1]+1) % 8
	if not can_move:
	continue
	# 비어 있을 경우 - 해당 위치로 이동
	if maps[ny][nx][0] == 0:
	maps[ny][nx] = maps[y][x]
	fish_dict[f_num] = (ny, nx)
	maps[y][x] = no_fish()
	else:
	# 기존 물고기와 자리바꿈
	o_num = maps[ny][nx][0]
	maps[ny][nx], maps[y][x] = maps[y][x], maps[ny][nx]
	fish_dict[f_num] = (ny, nx)
	fish_dict[o_num] = (y, x)
	# 상어가 이동할 다음 좌표
	ny, nx = y_s + dirs[shark_heading][0], x_s + dirs[shark_heading][1]
	# 다음 좌표로 이동이 가능한 경우
	while 0 <= ny < len(maps) and 0 <= nx < len(maps[0]):
	# 물고기가 있는 좌표일 경우 - dfs로 재귀탐색 진행
	if maps[ny][nx][0] != 0:
	dfs([ny, nx], deepcopy(maps), score+got_fish, deepcopy(fish_dict))
	# maps[ny][nx][0] == 0 인 경우는 해당 위치에 물고기가 없는 경우이다.
	# 다음 좌표로 이동
	ny, nx = ny + dirs[shark_heading][0], nx + dirs[shark_heading][1]
	# 더 이상 잡을 수 있는 물고기가 없는 경우 - 최댓값 갱신
	result = max(result, score+got_fish)
	return
	dfs([0,0], maps, 0, fish_dict)
	print(result)

view raw [백준] 청소년 상어.py hosted with ❤ by GitHub