[백준 2886] 자리 전쟁 (Python)

 

www.acmicpc.net/problem/2886

2886번: 자리 전쟁

문제풀이

R, C : 초기 입력 행, 열

board : 입력 값

chair : 의자 좌표(x, y)를 가지고 있는 리스트

people : 사람 좌표(x, y)를 가지고 있는 리스트

seated : 의자 인덱스 번호에 따른 의자 방문 횟수를 저장하는 리스트

finished : 사람 인덱스 번호에 따라 의자를 방문했는지 안했는지 판단하는 bool 리스트

# seated와 finished 는 문제조건 (1 <= R, C <= 100, R, C는 최소 1개 이상 존재)에 따라서 10001개가 아닌 10000개만 선언해도 충분하다.

ans : 결과값

chair_idx : 의자 인덱스 번호를 저장하는 리스트 => 의자방문 횟수(seated)를 계산할 때 사용

hq : 우선순위 큐

 

1. 우선순위 큐에 (사람과 의자 사이의 거리, 의자 인덱스, 사람 인덱스) 를 넣어준다.

- 우선순위큐를 이용하면 가장 앞에 있는 값(사람과 의자 사이의 거리)을 기준으로 작은 것부터 하나씩 뺄 수 있다. 

 

2. 문제 조건에 의하면 최소 1개의 의자와 1명의 사람은 반드시 존재하기 때문에 사전에 한번 우선순위큐에서 초기 값을 빼준다.

 

3. 우선순위 큐에서 값을 하나씩 빼면서 의자 방문 여부를 계산한다.

- 의자 인덱스를 가지고 있는 리스트(chair_idx)를 하나 선언하여 리스트 안에 있는 값을 통해 의자 방면 여부를 계산한다.

- 우선순위 큐에서 pop 한 의자 idx(nc)와 사람 idx(np)에서 해당 사람(np)이 아직 방문한 의자가 없고(not finished[np]), pop한 의자(nc)가 아직 어떤 사람에게도 방문되지 않았다면(not seated[nc]) 의자 인덱스 리스트(chair_idx)에 해당 의자 인덱스(nc)를 넣어준다.

- 특정 의자가 2번이상 방문되었다면 두 명 이상의 사람이 해당 의자를 두고 싸움을 하는 것이므로 ans 값을 1 증가한다.

 

4. 우선순위 큐를 모두 비우고 나서 chair_idx에 값이 남아있다면 한번 더 의자 방문 여부를 계산해준다.

 

 

코드

import sys
import heapq

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

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

if __name__ == '__main__':
    R, C = map(int, sys.stdin.readline().split())
    board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(R)]
    chair, people = [], []
    seated = [0] * 10000
    finished = [False] * 10000
    ans = 0
    chair_idx = []
    hq = []
    for i in range(R):
        for j in range(C):
            if board[i][j] == 'X':
                people.append((i, j))
            elif board[i][j] == 'L':
                chair.append((i, j))
    # 각 사람과 의자 사이의 거리, 사람 인덱스, 의자 인덱스를 우선순위큐에 넣어준다.
    for pidx, person in enumerate(people):
        px, py = person[0], person[1]
        for cidx, ch in enumerate(chair):
            cx, cy = ch[0], ch[1]
            dist = (px - cx) ** 2 + (py - cy) ** 2
            heapq.heappush(hq, (dist, pidx, cidx))

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

    while hq:
        nd, np, nc = heapq.heappop(hq)
        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] = True # 사람 인덱스 True로 변경
    if chair_idx: # 남아있는 계산되지 않은 의자 인덱스가 있으면
        cal(chair_idx) # 계산
    print(ans)

 

결과

 

 

위 풀이는 '라이온납시오' 님의 C++ 풀이를 파이썬으로 재풀이한 코드입니다.

https://imnotabear.tistory.com/286

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!