그리디/자리이동

Q·2021년 10월 16일
0

알고리즘/백준

목록 보기
70/70

문제 설명


문제

R x C의 형태를 지닌 전차 안에는 의자와 사람들의 정보들이 주어진다. 사람들은 다리가 아픈 것을 매우 싫어하기 때문에 빈 의자가 보이면 무조건 앉으려고 한다.

하지만 나보다 의자에 가까이 있는 사람이 보이면, 그 사람이 먼저 앉는다는 것을 알기 때문에 양보할 수밖에 없다.

만약, 나보다 의자에 가까이 있는 사람은 없지만, 같은 거리에 있는 사람이 있으면 서로 자리를 차지하려고 할 것이므로, 그 자리는 전쟁터가 될 것이다. (심지어 모든 사람들은 싸움에 자신있기 때문에, 이러한 전쟁터를 거부하지 않는다(!) )

여러분들은 이 전차의 정보가 주어질 때, 전쟁터가 될 자리의 수를 세어주면 된다.

A행 B열에서 C행 D열과의 떨어진 거리 Dist는 다음과 같은 유클리드 거리로 계산된다.

Dist² = (A-C)² + (B-D)²

입력

첫 줄에는 R과 C가 입력된다. (1 ≤ R ≤ 100) and (1 ≤ C ≤ 100)

이후 R개의 줄에 걸쳐 문자가 C개씩 주어진다. 이 문자는 '.' (빈 공간), 'X' (사람), 'L' (좌석) 만 주어지는 것이 보장된다.

'X'와 'L' 문자는 적어도 하나 이상이 주어짐이 보장되고, 하나의 'X' 문자와 같은 거리에 떨어진 'L'은 2개 이상 존재하지 않음이 보장된다.

출력

전쟁터의 수를 출력하면 된다.


문제링크

전체 코드

import sys
import heapq

input = sys.stdin.readline

def cal(chair_idx):
    # 의자 번호 인덱스를 통해 의자 방문 횟수 계산
    global ans

    for i in range(len(chair_idx)):
        cidx = chair_idx[i]
        seated[cidx] += 1 
        if seated[cidx] == 2:
            ans += 1

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

matrix = []
for _ in range(r):
    matrix.append(list(input().strip()))

chair = []
people = []
seated = [0] * 10000
finished = [0] * 10000
ans = 0
chair_idx = []
heap = []
for i in range(r):
    for j in range(c):
        if matrix[i][j] == 'X':
            people.append([i, j])
        elif matrix[i][j] == 'L':
            chair.append([i, j])

# 각 사람과 의자 사이의 거리, 사람 인덱스, 의자 인덱스를 우선순위큐에 넣어준다.
for i, person in enumerate(people): 
    px, py = person[0], person[1]
    for j, ch in enumerate(chair):
        cx, cy = ch[0], ch[1]
        dist = (px - cx)**2 + (py - cy)**2
        heapq.heappush(heap, (dist, i, j))

# 최소 1개의 의자와 1명의 사람이 있기 때문에 미리 한번 heappop을 해준다.
dist, psx, chx = heapq.heappop(heap) 
chair_idx.append(chx)  # chair_idx에 값이 들어갔다는 것은 어떤 사람이 의자를 방문하는 경우

finished[psx] = 1

while heap:
    nd, np, nc = heapq.heappop(heap)
    if dist != nd: # 거리가 이전 것과 다르면
        dist = nd # 거리변경
        if chair_idx: # 기존에 계산하지 않은 의자 인덱스가 남아있으면
            cal(chair_idx) # 의자 인덱스를 가지고 의자 방문 계산
            chair_idx.clear()
    if not seated[nc] and not finished[np]: # 아직 방문하지 않은 의자가 있고 그 사람이 한번도 어떤 의자를 방문한적 없으면
        chair_idx.append(nc) # 의자 인덱스 추가
        finished[np] = 1 # 사람 인덱스 True로 변경

if chair_idx: # 남아있는 계산되지 않은 의자 인덱스가 있으면
    cal(chair_idx) # 계산

print(ans)

해결 방법

  • 사람의 인덱스와 의자의 인덱스를 만들어서 각 사람과 각 의자 사이의 거리를 기준으로 우선순위큐에 넣어준다(dist, person_idx, chair_idx)
  • 우선순위큐에 있는 값을 하나씩 빼면서 의자별로 사람 방문 여부 계산한다.
  • 큐를 빠져나오고 나서도 남아있는 의자의 인덱스가 있으면 모두 계산한다.
profile
Data Engineer

0개의 댓글