[백준] 16236번: 아기 상어 - 파이썬

문제 보기

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

16236번: 아기 상어

 

 

 

 

---

 

풀이 및 코드

2차원 배열에서의 bfs를 이용한 완전 탐색 문제로 기존에 많이 나온 문제였다. 특별한 점은 해당 조건이었다.

• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

 

필자는 상좌우하 순으로 물고기를 찾아 해결하고자 했다. 하지만 depth가 쌓이면서 꼭 상좌우하 순으로 물고기를 찾지 않는 다는 것을 깨달았고 같은 거리의 물고기들을 모두 찾은 후에 조건문으로 물고기를 선별하는 방식으로 코드를 수정했다.

 

 

https://www.acmicpc.net/board/view/100687

글 읽기 - 【아기 상어】 예제 시뮬레이션

개인 적으로 큰 도움을 받았던 글이다. 테스트 케이스의 중간 과정들을 정리해 주신 글이다. 만일 코드를 작성하다가 실패하고 포스팅을 방문하였다면 해당 글을 읽어보는 것도 큰 도움이 될 것이다.

 

 

 

	from collections import deque
	n = int(input())
	area = [list(map(int, input().split())) for _ in range(n)]
	size = 2
	dy = [-1,0,0,1]
	dx = [0,-1,1,0]
	# 처음 상어 위치 찾기
	for i in range(n):
	for j in range(n):
	if area[i][j] == 9:
	y,x = i,j
	# 물고기 한마리 먹는 과정
	def bfs(y, x, size, cnt):
	dq = deque()
	dq.append([y,x])
	checked = [[0 for _ in range(n)] for _ in range(n)]
	period = 0
	res = []
	while dq:
	# 거리를 한칸 증가시킨 후 탐색
	period += 1
	for _ in range(len(dq)):
	y, x = dq.popleft()
	for d in range(4):
	ny, nx = y + dy[d], x + dx[d]
	# NxN에서 벗어나지 않으며 이전에 방문하지 않은 곳
	if 0 <= ny < n and 0 <= nx < n and checked[ny][nx] == 0:
	# 해당 지역에 물고기 여부와 크기에 따른 조건문
	if area[ny][nx] == size or area[ny][nx] == 0:
	checked[ny][nx] = 1
	dq.append([ny, nx])
	elif area[ny][nx] > size:
	continue
	else:
	# 먹을 수 있다면 res에 저장
	res.append([ny, nx])
	# res에 저장된 값이 있다면 상, 좌 기준에 맞추어 하나 선택
	if len(res) > 0:
	y, x = n, n
	for ny, nx in res:
	if ny < y or (ny == y and nx < x):
	y, x = ny, nx
	return period, y, x
	return 0, -1, -1
	time = 0
	size = 2
	cnt = 0
	while True:
	area[y][x] = 0
	# 물고기 찾는 데 걸린 시간, 물고기의 위치
	period, y, x = bfs(y, x, size, cnt)
	# 탐색하는 데 걸린 시간 업데이트
	if period == 0:
	print(time)
	break
	time += period
	cnt += 1
	if cnt == size:
	size += 1
	cnt = 0

view raw 16236.py hosted with ❤ by GitHub

 

 

 

 

 

해당 문제는 삼성 기출 문제로 solved.ac 기준 gold3에 랭크되어 있다.