AndroidTeacher

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

문제에서 주어진 대로, N개의 집에 C개의 공유기를 설치한다.

이 때, 가장 인접한 두 공유기 사이의 거리가 최대 가 되도록 해야 한다.

즉, 집의 좌표가 [ 1, 2, 4, 8, 9 ] 이고 공유기를 3개 설치 할 때, 공유기를 1, 4, 8 혹은 1, 4, 9 에 설치를 해야

가장 인접한 두 공유기 사이의 거리(1, 4)가 3이 되고, 이 3 보다 작게 설치를 할 수는 없다.

그렇다면, 공유기를 설치해야 될 집은 어떻게 찾아야 할까?

가장 간단한 방법으로는 순차 탐색으로 앞에서 부터 일일이 설치 집을 탐색해보며 실행하는 방법이 있지만,

가장 비효율적인 방법이며 분명 시간 제한 오류가 난다.

이러한 탐색 문제를 가장 빠르게 푸는 방법은 바로 이진 탐색(Binary Search) 이다.

이진 탐색을 쉽게 설명하자면,

예를들어, 1 부터 100까지의 숫자 사이에서 랜덤으로 정해진 숫자 하나를 맞추는 게임을 한다고 하자.

이 때 내가 부를 수 있는 숫자의 횟수는 3회이며, 숫자를 외칠 때 마다 정답이 그 숫자보다 작은지 큰지 맞는지 확인할 수 있다. 랜덤으로 정해진 숫자는 80이고, 나는 이 정답을 모르는 상태라고 가정하자.

처음엔 당연히 절반인 50을 부르는게 좋을 것이다. 이 때 정답이 50보다 크기 때문에 출제자는 50보다 크다고 알려 줄 것이며 그 다음에는 50보다 작은 부분은 검사할 필요가 없다. 그래서 그 다음엔 50과 100의 절반인 75를 부른다.

만약 75보다도 크다면 또 75보다 작은 부분은 검사할 필요가 없다.

이런 식으로 절반 씩 쪼개가며 탐색할 부분을 좁혀가는 방법이다.

만약 순차 탐색으로 진행했다면 1부터 80까지 80번을 실행해야 하지만, 이진 탐색을 실행하면 불과 5회 정도 만에 답을 찾아낼 수 있는 것이다.

이 방법으로 문제를 진행해보면

1. array라는 리스트에 집들의 좌표를 입력받은 후에 정렬.

2. start = 1, end = array[-1] - array[0] 으로 설정. ( 시작값은 최소 거리, 끝 값은 최대 거리 )

3. 앞 집부터 공유기 설치

4. 설치할 수 있는 공유기 개수가 c개를 넘어가면 더 넓게 설치할 수 있다는 이야기 이므로 설치거리를 mid + 1로 설정하여 다시 앞집부터 설치.

5. c개를 넘어가지 않는다면 더 좁게 설치해야 한다는 이야기 이므로 mid - 1로 설정.

위의 과정을 반복실행하면 정답을 얻을 수 있다.

코드는 다음과 같다.

n, c = map(int, input().split())

array = []
for i in range(n):
    array.append(int(input()))

array.sort()


def binary_search(array, start, end):
    while start <= end:
        mid = (start + end) // 2
        current = array[0]
        count = 1

        for i in range(1, len(array)):
            if array[i] >= current + mid:
                count += 1
                current = array[i]

        if count >= c:
            global answer
            start = mid + 1
            answer = mid
        else:
            end = mid - 1


start = 1
end = array[-1] - array[0]
answer = 0

binary_search(array, start, end)
print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

어렸을 때 해봤던 '뿌요뿌요' 게임을 구현한다고 생각하면 될 것 같다.

코드의 풀이 방식은 다음과 같다.

1. 맵(graph)을 돌면서 '.'이 아닌 것(뿌요)을 발견하면 BFS를 실행한다.

2. BFS로 진입하여 현재 터뜨릴 수 있는 뿌요를 모두 터뜨려 준다.

3. 뿌요가 터졌기 때문에 맵을 한번 정리해준다(gravity)

4. 터뜨릴 수 있는 뿌요가 계속 남아있을 때 까지 위 과정을 반복한다.

다만 주의 할 점은!

문제에도 명시되어 있지만 동시에 두 종류 이상의 뿌요가 터져도 한번의 연쇄만 추가 해야 한다는 것이다.

해당 설명은 코드 아래에도 다시 명시해 놓았다.

from collections import deque

graph = []

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

result = 0


def bfs(a, b, c):
    queue = deque()
    queue.append((a, b))

    pang = deque()
    pang.append((a, b))

    visited = [[False] * 6 for _ in range(12)]
    visited[a][b] = True
    count = 1
    flag = 0

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > 11 or ny < 0 or ny > 5:
                continue
            if graph[nx][ny] == c and not visited[nx][ny]:
                queue.append((nx, ny))
                pang.append((nx, ny))
                visited[nx][ny] = True
                count += 1

    if count >= 4:
        flag = 1

        for x, y in pang:
            graph[x][y] = "."

    return flag


def gravity():
    for y in range(6):
        queue = deque()
        for x in range(11, -1, -1):
            if graph[x][y] != '.':
                queue.append(graph[x][y])
        for x in range(11, -1, -1):
            if queue:
                graph[x][y] = queue.popleft()
            else:
                graph[x][y] = '.'


for i in range(12):
    graph.append(list(input()))


while True:
    chk = 0
    for i in range(12):
        for j in range(6):
            if graph[i][j] != '.':
                chk += bfs(i, j, graph[i][j])

    if chk == 0:
        print(result)
        break
    else:
        result += 1
    gravity()

# 처음에는 result를 bfs함수 안에서 global 변수로 선언하여
# 팡이 될 때 마다 +1을 해주는 방식으로 하였는데
# 이렇게 해주면, 동시에 두 뿌요가 터지는 경우에도 두 개를 카운트를 해 준다.
# 하지만 문제에서, 동시에 여러개의 뿌요가 터질 때는 한 번 카운트를 해주라고 명시했기 때문에
# bfs 함수 안이 아닌, 바깥에서 +1을 해주는 방식으로 변경하였다. 이렇게 하니 정답이 나온다.

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !