[5주차] 알고리즘 과제

<백준 1697번>

 

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

1697번: 숨바꼭질

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

수빈이가 동생에게 가는 가장 빠른 시간을 출력하려면, N에서 K까지 가장 빨리 가는 방법을 찾아야 한다. 이는 BFS(너비 우선 탐색)을 이용하여 최소 시간을 구할 수 있다. 

 

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

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색

 

 

from collections import deque

def bfs(n, k):
    q = deque()
    q.append((n, 0))
    visited = [False] * 100001
    visited[n] = True

    while q:
        x, time = q.popleft()

        if x == k:
            return time

        if x-1 >= 0 and not visited[x-1]:
            q.append((x-1, time+1))
            visited[x-1] = True
        if x+1 <= 100000 and not visited[x+1]:
            q.append((x+1, time+1))
            visited[x+1] = True
        if 2*x <= 100000 and not visited[2*x]:
            q.append((2*x, time+1))
            visited[2*x] = True

n, k = map(int, input().split())
print(bfs(n, k))

 

 

 

먼저, 수빈이의 현재 위치와 동생의 위치를 입력 받습니다.

그리고 BFS 함수를 정의합니다. 큐를 이용하여 너비 우선 탐색을 진행합니다.

수빈이의 위치와 시간(초)을 큐에 저장합니다. 이때, 방문한 위치는 visited 리스트에 체크합니다.

큐에서 꺼낸 위치가 동생의 위치와 같다면 해당 시간을 반환하고, 그렇지 않으면 해당 위치에서 가능한 이동 방법을 모두 큐에 저장합니다.

이때, 범위를 벗어나지 않도록 조건을 체크하고, 이미 방문한 위치인 경우에는 큐에 추가하지 않습니다.

마지막으로, 입력 받은 수빈이와 동생의 위치를 인자로 넘겨 BFS 함수를 호출하고 결과를 출력합니다.

 

 

 

<백준 4716-풍선>

 

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

문제

전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다.

풍선은 방 A와 방 B에 보관되어 있다. 대회에 참가한 팀의 수는 총 N개이고, 앉아있는 자리는 서로 다르다. 어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다. 

각 팀에게 달아줘야 하는 풍선의 수와 방 A와 B로부터의 거리가 주어진다. 이때, 모든 풍선을 달아주는데 필요한 이동 거리의 최솟값을 출력한다. 대회에서 풍선을 달아주는 사람은 매우 많고, 풍선은 한 가지 색상을 여러 개 달아준다고 가정한다. 풍선을 달기 위해 이동해야하는 거리는 팀이 A와 B로부터 떨어진 거리와 같다. 풍선을 달아주는 사람은 한 번에 풍선 하나만 들고 이동할 수 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000) 

다음 N개 줄에는 팀에게 달아줘야하는 풍선의 수 K와 방 A로부터 떨어진 거리 DA, B로부터 떨어진 거리 DB (0 ≤ DA, DB ≤ 1,000)가 주어진다. 풍선이 부족한 경우는 없다. 즉, Σi Ki ≤ A+B.

입력의 마지막 줄에는 0이 세 개 주어진다.

출력

각 테스트 케이스에 대해서, 모든 팀에게 풍선을 달아주기 위해 필요한 이동 거리의 최솟값을 한 줄에 하나씩 출력한다. 이때, 풍선을 달아주고 방 A나 B로 돌아오는 거리는 포함하지 않는다. 즉, 방 A와 B에서 팀으로 이동하는 거리만 포함한다.

 

 

 

이 문제는 각 팀이 받아야 하는 풍선의 수와 각 방으로부터의 거리 정보를 이용하여, 팀들을 방 A 혹은 방 B 중에서 가장 가까운 방으로 보내주면서 풍선을 달아주면 됩니다. 구글링 해보니 그리디 알고리즘을 이용하여 해결할 수 있다고 합니다.

그리디 알고리즘(Greedy Algorithm)은 최적해를 구하는 데 사용되는 근시안적인 방법론으로, 각 단계에서 지금 상황에서 가장 좋아 보이는 선택을 하면서 최종적인 해답을 구하는 알고리즘입니다. 이 알고리즘은 매 순간마다 최적의 선택을 하기 때문에 뒤에 있는 선택들을 고려하지 않는다는 특징이 있습니다. 그렇기 때문에 항상 최적해를 보장하지는 않지만, 대부분의 경우 최적해를 찾는데 효과적인 알고리즘입니다.

 

while True 루프를 사용하여 입력을 반복적으로 받아오고, 각 테스트 케이스에서는 팀의 수 n과 방 A와 B에 보관되어있는 풍선의 수 a, b를 입력받습니다. 다음 n개의 줄에서는 각 팀에게 달아줘야하는 풍선의 수 k와 방 A로부터 떨어진 거리 da, B로부터 떨어진 거리 db를 입력받습니다.

 

 

 

 

while True:
    n, a, b = map(int, input().split())

    if n == a == b == 0:
        break

    teams = []
    for i in range(n):
        k, da, db = map(int, input().split())
        teams.append((k, da, db))

    # 각 팀을 방 A 혹은 방 B로 보내주면서 거리 합 구하기
    total_dist = 0
    a_cnt = 0
    b_cnt = 0
    for k, da, db in sorted(teams, key=lambda x: abs(x[1] - x[2]), reverse=True):
        if da < db and a_cnt < a:
            a_cnt += 1
            total_dist += da
        elif b_cnt < b:
            b_cnt += 1
            total_dist += db

    print(total_dist)

 

참고: https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html