카테고리 없음

[6주차] 알고리즘

jwk818 2023. 11. 8. 11:23

<백준 16236번>

 

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

 

16236번: 아기 상어

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

www.acmicpc.net

 

 

문제

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

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

예제 입력 1 복사

3
0 0 0
0 0 0
0 9 0

예제 출력 1 복사

0

예제 입력 2 복사

3
0 0 1
0 0 0
0 9 0

예제 출력 2 복사

3

 

 

이 문제는 아기 상어가 주어진 공간에서 물고기를 먹고 성장하는 과정을 시뮬레이션하는 문제입니다. 주어진 조건에 따라 아기 상어가 물고기를 잡아먹을 수 있는 시간을 구해야 합니다.

우선, 입력을 받아서 공간의 상태와 아기 상어의 위치를 파싱합니다. 그리고 아기 상어의 크기와 먹은 물고기 수, 아기 상어의 위치, 공간의 크기 등을 변수로 초기화합니다.

다음으로 아기 상어가 먹을 수 있는 물고기가 있는지 확인하고, 먹을 수 있는 물고기가 없을 때까지 다음 작업을 반복합니다:

1. BFS (Breath-First Search)를 사용하여 아기 상어의 위치로부터 먹을 수 있는 물고기까지의 거리를 계산하고, 가장 가까운 물고기를 찾습니다.
2. 가장 가까운 물고기를 찾으면 그 물고기를 먹고, 먹은 물고기 수를 증가시킵니다.
3. 아기 상어의 크기와 먹은 물고기 수가 같아지면 아기 상어의 크기를 1 증가시키고 먹은 물고기 수를 초기화합니다.
4. 먹은 물고기 수가 아기 상어의 크기와 같아지면 아기 상어의 크기를 다시 1 증가시킵니다.
5. 아기 상어의 위치를 업데이트하고, 이동한 시간을 기록합니다.

모든 먹을 수 있는 물고기를 먹었을 때까지 반복하고, 걸린 시간을 출력하면 된다.



```python
from collections import deque

N = int(input())
space = [list(map(int, input().split())) for _ in range(N)]

shark_size = 2
shark_x, shark_y = 0, 0
shark_eat = 0
time = 0

for i in range(N):
    for j in range(N):
        if space[i][j] == 9:
            shark_x, shark_y = i, j
            space[i][j] = 0

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

while True:
    min_dist = 1e9
    min_x, min_y = 0, 0
    visited = [[False] * N for _ in range(N)]
    queue = deque([(shark_x, shark_y, 0)])

    while queue:
        x, y, dist = queue.popleft()

        if 0 < space[x][y] < shark_size:
            if dist < min_dist:
                min_dist = dist
                min_x, min_y = x, y
            elif dist == min_dist and x < min_x:
                min_x, min_y = x, y
            elif dist == min_dist and x == min_x and y < min_y:
                min_x, min_y = x, y

        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and space[nx][ny] <= shark_size:
                visited[nx][ny] = True
                queue.append((nx, ny, dist + 1))

    if min_dist == 1e9:
        break

    shark_x, shark_y = min_x, min_y
    space[shark_x][shark_y] = 0
    shark_eat += 1

    if shark_eat == shark_size:
        shark_size += 1
        shark_eat = 0

    time += min_dist

print(time)
```

BFS(너비 우선 탐색) 알고리즘이란? 

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.


사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색

 

 

from collections import deque

N = int(input())  # 공간의 크기 N을 입력 받음
space = [list(map(int, input().split())) for _ in range(N)]  # 공간의 상태를 2D 리스트로 입력 받음

shark_size = 2  # 아기 상어의 크기를 초기화합니다.
shark_x, shark_y = 0, 0  # 아기 상어의 위치를 초기화
shark_eat = 0  # 아기 상어가 먹은 물고기 수를 초기화
time = 0  # 아기 상어가 먹을 때까지 걸린 시간을 초기화

# 아기 상어와 공간의 초기 상태를 찾아서 위치와 상태를 초기화
for i in range(N):
    for j in range(N):
        if space[i][j] == 9:
            shark_x, shark_y = i, j
            space[i][j] = 0

dx = [-1, 1, 0, 0]  # 상하좌우 방향 이동을 위한 x 좌표 변화
dy = [0, 0, -1, 1]  # 상하좌우 방향 이동을 위한 y 좌표 변화

while True:
    min_dist = 1e9  # 가장 가까운 물고기까지의 거리를 나타내는 변수를 초기화
    min_x, min_y = 0, 0  # 가장 가까운 물고기의 위치를 초기화
    visited = [[False] * N for _ in range(N)]  # 방문 여부를 나타내는 2D 리스트를 초기화
    queue = deque([(shark_x, shark_y, 0)])  # BFS를 위한 큐를 초기화 (x, y, 현재 거리)

    while queue:
        x, y, dist = queue.popleft()  # 큐에서 아기 상어의 현재 위치와 거리를 가져옴

        if 0 < space[x][y] < shark_size:  # 아기 상어보다 작은 물고기가 있는 경우
            if dist < min_dist:
                min_dist = dist
                min_x, min_y = x, y
            elif dist == min_dist and x < min_x:
                min_x, min_y = x, y
            elif dist == min_dist and x == min_x and y < min_y:
                min_x, min_y = x, y

        for d in range(4):  # 상하좌우 방향에 대해 탐색
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and space[nx][ny] <= shark_size:
                visited[nx][ny] = True
                queue.append((nx, ny, dist + 1))

    if min_dist == 1e9:  # 먹을 수 있는 물고기가 없을 때
        break

    shark_x, shark_y = min_x, min_y  # 아기 상어의 위치를 업데이트
    space[shark_x][shark_y] = 0  # 먹은 물고기의 위치를 빈 칸으로 변경
    shark_eat += 1  # 아기 상어가 먹은 물고기 수를 증가시킵니다.

    if shark_eat == shark_size:  # 아기 상어가 크기만큼 물고기를 먹었을 때
        shark_size += 1  # 아기 상어의 크기를 증가시킵니다.
        shark_eat = 0  # 먹은 물고기 수를 초기화

    time += min_dist  # 아기 상어가 이동한 시간을 누적

print(time)  # 아기 상어가 모든 먹을 수 있는 물고기를 먹었을 때 걸린 시간을 출력

 

 

 

 

 

<백준 9934번>

 

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

 

9934번: 완전 이진 트리

상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래

www.acmicpc.net

 

문제

상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다. 또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다.

 

깊이가 2와 3인 완전 이진 트리

상근이는 도시에 있는 모든 빌딩에 들어갔고, 들어간 순서대로 번호를 종이에 적어 놓았다. 한국으로 돌아온 상근이는 도시가 어떻게 생겼는지 그림을 그려보려고 하였으나, 정확하게 기억이 나지 않아 실패했다. 하지만, 어떤 순서로 도시를 방문했는지 기억해냈다.

  1. 가장 처음에 상근이는 트리의 루트에 있는 빌딩 앞에 서있다.
  2. 현재 빌딩의 왼쪽 자식에 있는 빌딩에 아직 들어가지 않았다면, 왼쪽 자식으로 이동한다.
  3. 현재 있는 노드가 왼쪽 자식을 가지고 있지 않거나 왼쪽 자식에 있는 빌딩을 이미 들어갔다면, 현재 노드에 있는 빌딩을 들어가고 종이에 번호를 적는다.
  4. 현재 빌딩을 이미 들어갔다 온 상태이고, 오른쪽 자식을 가지고 있는 경우에는 오른쪽 자식으로 이동한다.
  5. 현재 빌딩과 왼쪽, 오른쪽 자식에 있는 빌딩을 모두 방문했다면, 부모 노드로 이동한다.

왼쪽 그림에 나와있는 마을이라면, 상근이는 2-1-3 순서대로 빌딩을 들어갔을 것이고, 오른쪽 그림의 경우에는 1-6-4-3-5-2-7 순서로 들어갔을 것이다. 상근이가 종이에 적은 순서가 모두 주어졌을 때, 각 레벨에 있는 빌딩의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 K (1 ≤ K ≤ 10)가 주어진다.

둘째 줄에는 상근이가 방문한 빌딩의 번호가 들어간 순서대로 주어진다. 모든 빌딩의 번호는 중복되지 않으며, 구간 [1,2K)에 포함된다.

출력

총 K개의 줄에 걸쳐서 정답을 출력한다. i번째 줄에는 레벨이 i인 빌딩의 번호를 출력한다. 출력은 왼쪽에서부터 오른쪽 순서대로 출력한다.

예제 입력 1 복사

2
2 1 3

예제 출력 1 복사

1
2 3

 

 

이 코드는 주어진 방문 순서를 이용하여 이진 트리를 구성하고, 각 레벨의 빌딩 번호를 BFS(너비 우선 탐색) 방식으로 출력하는 것으로 해결할 수 있다.

 

import sys
input = sys.stdin.readline

K = int(input())  # 트리의 깊이 K를 입력 
_input = list(map(int, input().split()))  # 방문한 빌딩의 번호를 리스트로 입력 
tree = [[] for _ in range(K)]  # 각 레벨의 빌딩을 저장할 리스트를 초기화

# 이진 트리를 BFS 방식으로 구성하는 함수
def makeTree(arr, x):
    mid = (len(arr) // 2)
    tree[x].append(arr[mid])  # 현재 레벨의 중간 빌딩을 추가
    if len(arr) == 1:
        return
    makeTree(arr[:mid], x + 1)  # 왼쪽 서브트리를 구성
    makeTree(arr[mid + 1:], x + 1)  # 오른쪽 서브트리를 구성

makeTree(_input, 0)  # 이진 트리를 빌드

# 각 레벨의 빌딩 번호를 출력
for i in range(K):
    print(*tree[i])