[백준/삼성] 16236 아기상어

2022. 2. 3. 18:17·Algorithm (PS)
728x90

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

 

16236번: 아기 상어

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

www.acmicpc.net

 

유형 : BFS/ DFS (나는 BFS로 풀었당)

어려웠던 부분은 '최단 거리'를 어떻게 구하냐는 것이다. BFS로 최단거리를 구하는 방법을 꼭 기억해두자 !!

 

현재 위치 (x, y)에서 ->

상하좌우 를 확인하는데 (for 문으로 확인 nx = x + dx[i], ny = y + dy[i])->

0 ~ n 의 범위 안에 있어야 하며 (0 <=nx < n and 0 <= ny < n) ->

아직 방문되지 않았다면 (dist[nx][ny] == -1) -> 

dist[nx][ny] = dist[x][y] + 1

 

한 지점 (상어의 위치) 에서 다른 모든 칸들에 도달하는 '최단 거리' 테이블을 구한다. 

도달 할 수 있는 칸에 있는 '물고기' 들 중에서 자기자신보다 작은 사이즈이며, 가장 가까이에 있는 물고기를 먹을 수 있다. 

이 가장 가까이에 있는 물고기를 어떻게 구해야 할지가 어려웠는데, -> 최단 거리 테이블을 구한 다음에, 하나씩 조건에 맞게 값을 걸러낸 다음 가장 작은 값과 현재 위치의 최단거리를 비교해서 min_dist에 저장한다. 

# 아기 상어
from collections import deque

n = int(input())
size = 2 # 현재 상어의 크기
result = 0
array = []
INF = int(1e9)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(n):
    data = list(map(int, input().split()))
    array.append(data)

sx, sy = 0, 0 # shark position

for i in range(n):
    for j in range(n):
        if array[i][j] == 9: # 상어 위치
            sx = i
            sy = j
            array[i][j] = 0

def distance(): # 최단 거리 계산
    dist = [[-1]*n for _ in range(n)] # 최단 거리 테이블
    q = deque()
    q.append((sx, sy))
    dist[sx][sy] = 0 # 시작 지점은 최단거리 0 이라고 한다
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and dist[nx][ny] == -1 and array[nx][ny] <= size: # 지나갈 수 있는가 확인
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

    return dist


def find(dist): # 최단 거리가 주어졌을 때 먹을 물고기를 찾는 함수
    x, y = 0, 0
    min_dist = INF

    for i in range(n):
        for j in range(n):
            if dist[i][j] != -1 and 1 <= array[i][j] < size: # 먹을 수 있는 물고기인지 확인
                if min_dist > dist[i][j]:
                    min_dist = dist[i][j]
                    x, y = i, j
    if min_dist == INF:
        return None # 먹을 수 있는 물고기가 없다
    return x, y, min_dist

eat = 0 # 지금 먹은 물고기 개수
while True:
    data = find(distance())
    if data == None:
        print(result)
        break
    else:
        result += data[2] # min_dist 만큼 물고기에 도달하는데 시간이 걸릴 것이므로
        sx, sy = data[0], data[1] # 새로운 위치로 이동
        array[sx][sy] = 0 # 먹었으면 0 으로 바꿔준다.
        eat += 1
        if eat >= size:
            size += 1
            eat = 0

 

728x90

'Algorithm (PS)' 카테고리의 다른 글

[백준] 12865 평범한 배낭, Knapsack Problem  (0) 2022.02.03
[프로그래머스] 크레인 인형 뽑기  (0) 2022.02.03
[백준] 1699 제곱수의 합 <부제: 너무 느린 파이썬 극복하기;;>  (0) 2022.02.01
[백준] 11054 가장 긴 바이토닉 부분 수열 in python  (0) 2022.01.31
[백준] 1991 트리 순회  (0) 2022.01.28
'Algorithm (PS)' 카테고리의 다른 글
  • [백준] 12865 평범한 배낭, Knapsack Problem
  • [프로그래머스] 크레인 인형 뽑기
  • [백준] 1699 제곱수의 합 <부제: 너무 느린 파이썬 극복하기;;>
  • [백준] 11054 가장 긴 바이토닉 부분 수열 in python
minjiwoo
minjiwoo
Data Engineering과 Cloud Native 기술에 대해 Dive Deep 하는 플랫폼 엔지니어가 되는 것을 목표로 하고 있습니다. 경험과 공부한 내용을 기록하며 지속가능한 엔지니어가 되는 것이 꿈입니다.
minjiwoo
minji's engineering note
minjiwoo
전체
오늘
어제
  • 분류 전체보기 (613)
    • Data Engineering (42)
      • Apache Spark (11)
      • Databricks & Delta Lake (9)
      • Airflow (3)
      • SQL (6)
      • Trouble Shooting (2)
      • Hadoop (2)
      • MLOps (1)
    • Cloud Engineering (104)
      • AWS (23)
      • Linux 🐧 (29)
      • Docker 🐳 (21)
      • Kubernetes ⚙️ (20)
      • Ansible (10)
    • Computer Science (87)
      • 네트워크 (9)
      • 운영체제 (25)
      • 정보처리기사 (48)
      • CS 기술 면접 스터디 (3)
    • Programming Languages (27)
      • Python (17)
      • C와 C++ (10)
    • Backend (5)
      • Django (2)
    • 프로젝트 (2)
      • 테크포임팩트 (2)
    • iOS (11)
      • 레이블러리 (2)
    • Algorithm (PS) (275)
      • LeetCode (6)
    • 개발일기 (30)
      • 내돈내산 후기🎮 (3)
      • 개발자 취준생 (5)
      • Today I Learned (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • Hi there

인기 글

태그

  • docker
  • 리눅스
  • 스파크
  • Kubernetes
  • 카카오코딩테스트
  • 빅데이터
  • Swift
  • python
  • 쿠버네티스
  • 운영체제
  • SPARK
  • Databricks
  • 코딩테스트
  • 클라우드
  • ansible
  • 데이터엔지니어링
  • 백트래킹
  • 프로그래머스
  • Leetcode
  • linux
  • AWS
  • 백준
  • dp
  • 데이터브릭스
  • BFS
  • dfs
  • 데이터엔지니어
  • 파이썬
  • EC2
  • 알고리즘

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
minjiwoo
[백준/삼성] 16236 아기상어
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.