developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 시계열
  • 코테파이썬
  • ARIMA모형
  • 카카오코테
  • c++ 빌더 패턴
  • 삼성코테기출자바풀이
  • 삼성코테기출
  • Arima
  • MA모형
  • 카카오코테java풀이
  • 삼성코테준비
  • 삼성코테자바꿀팁
  • 삼성코테자바준비
  • SW역량테스트파이썬
  • AR모형
  • BOJ파이썬풀이
  • 삼성코테파이썬
  • 삼성코테구현문제추천
  • 운영체제인터럽트
  • 데이터분석
  • 시계열분석
  • 통계학
  • 삼성코테파이썬풀이
  • 삼성코테파이썬준비
  • SW역량테스트파이썬풀이
  • 백준파이썬풀이
  • 삼성코테자바풀이
  • 삼성코테구현풀이
  • 통계분석
  • c++디자인패턴

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 아기 상어 16236번 (python)

2021. 10. 16. 20:59

❓ 문제 - 백준 아기 상어 16236번 - python 풀이법

출처 

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

 

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

www.acmicpc.net

 

 

📝 문제해결법

1. 이 문제는 BFS + 구현으로 풀었다.

  • 공간에 대한 정보를 입력받으면서 아기 상어가 존재하는 행,열을 저장하고, 처음에 아기상어가 존재하는 공간의 값을 0으로 바꿔준다.
  • 현재 아기 상어가 존재하는 행과 열에 대해서 BFS를 돌아서 현재 자신보다 크기가 작은 물고기가 있는지 탐색하고, 존재한다면 가장 가까운 애들부터 먹는다. (이때, 이동 거리를 answer에 더해줌) 먹으러 갔을 때 위치를 현재위치로 변경한다.
  • 먹었을 때 해당 공간의 물고기는 없애주고, eat 을 증가시켜준다. (eat은 아기 상어가 먹은 물고기) 만약 아기상어가 먹은 물고기의 수(eat)과 아기상어의 현재 크기가 같다면 아기 상어의 크기를 1 증가시켜고 eat은 0으로 초기화 해준다.
  • 계속 크기가 자신보다 작은 물고기를 먹으러 다니면서, 만약 현재 크기가 자신보다 작은 물고기를 더이상 먹을 수 없다면 break로 while문을 빠져와서 answer을 출력한다.

2. BFS

  • fish 리스트로 현재 아기 상어가 먹을 수 있는 물고기의 행,열 정보와 그 물고기까지의 이동 거리를 저장한다.
  • 현재 위치에서 4방향으로 탐색해서 , 범위를 넘지 않고 만약 방문되지 않은 곳에 물고기가 존재하는데 물고기의 크기가 아기 상어의 크기보다 작다면 fish 리스트에 append 해주며, 물고기 탐색 queue에 nx, ny를 append 해준다.
  • 그리고 탐색하는 공간이 빈칸(0) 이거나, 현재 아기 상어의 크기와 동일한 물고기가 존재한다면 아기상어가 지나갈 수 있기 때문에 탐색 queue에 nx, ny를 append 해준다.
  • 만약 먹을 수 있는 물고기가 존재(fish 리스트의 길이가 1이상) 이라면, sort를 통해 (최단 거리의 물고기 - 행이 가장 작은 위치 - 열이 가장 작은 위치) 현재 위치에서 가장 먹을 수 있는 최단 거리의 물고기 정보를 return 해준다.

 

💻 소스코드

# 아기 상어 - BOJ 16236
# BFS + 구현
from collections import deque
n = int(input())
s_x, s_y = -1, -1
s_level, eat = 2, 0
graph = []

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(n):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(n):
        if data[j] == 9:
            s_x, s_y = i, j


graph[s_x][s_y] = 0

def bfs(s_x, s_y, s_level):
    visited = [[False]*n for _ in range(n)]
    q = deque()
    q.append((s_x, s_y, 0))
    visited[s_x][s_y] = True
    fish = []
    while q:
        x, y, count = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                visited[nx][ny] = True
                if graph[nx][ny] != 0 and graph[nx][ny] < s_level:
                    fish.append((count+1, nx, ny))
                    q.append((nx, ny, count+1))
                    visited[nx][ny] = True
                elif graph[nx][ny] == 0 or graph[nx][ny] == s_level:
                    visited[nx][ny] = True
                    q.append((nx, ny, count+1))

    fish.sort()
    if fish:
        return [fish[0][1], fish[0][2], fish[0][0]]
    else:
        return []

answer = 0

while True:
    fish_eat = bfs(s_x, s_y, s_level)
    if fish_eat:
        x, y, move = fish_eat
        graph[x][y] = 0
        eat += 1
        answer += move
        if eat == s_level:
            s_level += 1
            eat = 0
        s_x, s_y = x, y
    else:
        break

print(answer)

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 낚시왕 17143번 (python)  (0) 2021.10.17
BOJ - 미세먼지 안녕! 17144번 (python)  (0) 2021.10.16
BOJ - 나무 재테크 16235번 (python)  (0) 2021.10.16
BOJ - 치킨 배달 15686번 (python)  (0) 2021.10.16
BOJ - 드래곤 커브 15685번 (python)  (0) 2021.10.16
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 낚시왕 17143번 (python)
    • BOJ - 미세먼지 안녕! 17144번 (python)
    • BOJ - 나무 재테크 16235번 (python)
    • BOJ - 치킨 배달 15686번 (python)
    developer-ellen
    developer-ellen

    티스토리툴바