Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 백준1026
- tensorflow
- 혁펜하임강의후기
- 패스트캠퍼스혁펜하임
- C++ 함수
- CUDA
- 조건문
- 패스트캠퍼스
- C++
- 반복문
- pytorch
- 1463
- AIDEEPDIVE
- cuDNN
- for문
- 백준1463
- 백준C++
- 혁펜하임
- 비교연산자
- 1로만들기
- 혁펜하임강의
- AI강의
- 9095
- C++ 공백 입력
- precision
- C++ 백준
- 혁펜하임AI
- c++ 기초
- 백준9095
- 백준
Archives
- Today
- Total
코딩하는 덕구 🐶
125. [삼성기출21]Python 백준 16236 번 아기상어 본문
728x90
안녕하세요 코딩하는 덕구입니다.
백준 16236 번 아기상어 입니다.
https://www.acmicpc.net/problem/16236
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
먼저 백준 16236 번 아기상어 코드입니다. 설명은 아래에 있습니다.
from collections import deque
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
candidate = []
def bfs(x, y):
visited = [[False for _ in range(N)] for _ in range(N)]
visited[x][y] = True
queue = deque()
queue.append([x, y, 0])
candidate = []
if board[x][y] == 9:
board[x][y] = 0
limit_time = 9999
while queue:
x, y, time = queue.popleft()
if time < limit_time:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if not visited[nx][ny]:
if board[nx][ny] == 0 or board[nx][ny] == shark_size:
visited[nx][ny] = True
queue.append([nx, ny, time + 1])
elif board[nx][ny] < shark_size:
visited[nx][ny] = True
candidate.append([nx, ny, time + 1])
limit_time = time + 1
return candidate
exp = 0
total_time = 0
shark_size = 2
for i in range(N):
for j in range(N):
if board[i][j] == 9:
x = i
y = j
while True:
candidate = bfs(x, y)
if len(candidate) == 0:
break
candidate.sort(key=lambda x : (x[0], x[1])) #조건에 맞는 순서로 정렬
x, y, time = candidate[0]#맨앞 후보 잡아먹기
board[x][y] = 9
exp += 1
if exp == shark_size: #상어 성장
shark_size += 1
exp = 0
total_time += time
print(total_time)
문제 접근
1. bfs를 통해 가까운 거리의 먹을 수 있는 물고기를 탐색합니다.
2. 조건에 맞는 물고기를 먹고 그 자리에서 다시 bfs를 반복합니다.
Python 코드 구현
bfs에 필요한 변수들을 선언합니다.
from collections import deque
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
candidate = []
맨 처음 상어의 위치를 찾고, 해당 위치부터 bfs를 실행합니다.
bfs는 가까운 먹이감들의 좌표, 거리를 담는 리스트를 return합니다.
bfs 실행 후 먹이를 먹는 순서로 리스트를 정렬하고, 먹이를 먹습니다.
또한 성장조건이 된다면 상어는 성장합니다.
먹을 수 있는 물고기가 없을때 까지 반복하고 답을 출력하면 됩니다.
exp = 0
total_time = 0
shark_size = 2
for i in range(N):
for j in range(N):
if board[i][j] == 9:
x = i
y = j
while True:
candidate = bfs(x, y)
if len(candidate) == 0:
break
candidate.sort(key=lambda x : (x[0], x[1])) #조건에 맞는 순서로 정렬
x, y, time = candidate[0]#맨앞 후보 잡아먹기
board[x][y] = 9
exp += 1
if exp == shark_size: #상어 성장
shark_size += 1
exp = 0
total_time += time
print(total_time)
bfs는 두가지 조건이 있습니다.
먹을 수 있는가, 없는가
만약 먹을 수 있다면 후보 리스트에 추가합니다.
먹을 수 없고, 지나갈 수 있다면 해당 위치에서 다시 탐색합니다.
이때 후보 리스트에 있는 먹있감보다 거리가 멀어지면 탐색하지 않습니다.
def bfs(x, y):
visited = [[False for _ in range(N)] for _ in range(N)]
visited[x][y] = True
queue = deque()
queue.append([x, y, 0])
candidate = []
if board[x][y] == 9:
board[x][y] = 0
limit_time = 9999
while queue:
x, y, time = queue.popleft()
if time < limit_time:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if not visited[nx][ny]:
if board[nx][ny] == 0 or board[nx][ny] == shark_size:
visited[nx][ny] = True
queue.append([nx, ny, time + 1])
elif board[nx][ny] < shark_size:
visited[nx][ny] = True
candidate.append([nx, ny, time + 1])
limit_time = time + 1
return candidate
파이썬 백준 16236 번 아기상어 최종 코드입니다.
from collections import deque
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
candidate = []
def bfs(x, y):
visited = [[False for _ in range(N)] for _ in range(N)]
visited[x][y] = True
queue = deque()
queue.append([x, y, 0])
candidate = []
if board[x][y] == 9:
board[x][y] = 0
limit_time = 9999
while queue:
x, y, time = queue.popleft()
if time < limit_time:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if not visited[nx][ny]:
if board[nx][ny] == 0 or board[nx][ny] == shark_size:
visited[nx][ny] = True
queue.append([nx, ny, time + 1])
elif board[nx][ny] < shark_size:
visited[nx][ny] = True
candidate.append([nx, ny, time + 1])
limit_time = time + 1
return candidate
exp = 0
total_time = 0
shark_size = 2
for i in range(N):
for j in range(N):
if board[i][j] == 9:
x = i
y = j
while True:
candidate = bfs(x, y)
if len(candidate) == 0:
break
candidate.sort(key=lambda x : (x[0], x[1])) #조건에 맞는 순서로 정렬
x, y, time = candidate[0]#맨앞 후보 잡아먹기
board[x][y] = 9
exp += 1
if exp == shark_size: #상어 성장
shark_size += 1
exp = 0
total_time += time
print(total_time)
백준 16236 번 아기상어 Python 코드였습니다.
감사합니다.
728x90
'알고리즘 문제 풀이' 카테고리의 다른 글
127. [삼성기출23]Python 백준 17143 번 낚시왕 (0) | 2023.06.13 |
---|---|
126. [삼성기출22]Python 백준 17144 번 미세먼지 안녕! (0) | 2023.06.12 |
124. [삼성기출20]Python 백준 16235 번 나무 재테크(시간 초과) (0) | 2023.06.08 |
123. [삼성기출19]Python 백준 16234 번 인구 이동 자세한 설명 (0) | 2023.06.05 |
122. [삼성기출18]Python 백준 5373 번 큐빙 자세한 설명 (0) | 2023.05.31 |