[알고리즘] 백준 21608 Python

 

분류

구현, (우선순위 큐)

혼자 힘으로 해결 했는가?

O

느낀 점

상어....만 보면 머리가 아파진다. 이 문제를 이번에 처음 푸려고 시도한 것은 아니다.

약 6개월 전에 해결을 해보고자 문제를 읽었지만 너무 머리가 복잡해져서 포기했다.

다시 도전하니 한번에 해결을 해서 기분이 좋았다.

 

이 문제에서 조건이 많아서 귀찮다. 어렵지는 않지만 귀찮고 과연 이게 될까? 라는 생각에 풀이를 시작하기가 꺼려진다.

 

이 문제에서 제일 짜증났던 부분은 아래와 같다.

---

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

그냥 순수하게 구현을 하는 것도 까다로운데 저 같을 경우에 대한 처리가 매우 짜증났다.

 

그러나 이를 해결하기 위한 방법이 머리속으로 떠올랐고

이는 바로 우선순위 큐를 사용하는 것 이었다.

 

그냥 간단히 인접한 학생의 수, 빈칸의 수를 우선순위로 두고 이중 for로 검사를 하면 자연스럽게

행과 열이 앞선 경우가 큐에 들어간다.

 

따라서 그냥 앞서서 들어온 경우가 우선이 되도록 우선순위를 결정해서 힙을 이용해서 큐에 담으면 된다.

 

그리고 파이썬,자바, C++ 모두 우선순위 큐를 라이브러리에서 제공하기 때문에

그냥 편하게 사용했다. 다만 힙에 담을 때 내가 원하는 기준대로 담기 위해 클래스를 만들었다.

---

 

내가 작성한 코드

from sys import stdin
import heapq


# (x,y) y = 인접한 빈칸 갯수, x = 인접한 선호 학생 명, z = 좌표
class MyHeap:
    def __init__(self):
        self.heap = []
        self.index = 0

    def push(self, item):
        heapq.heappush(self.heap, (-item[0], -item[1], self.index, item[2]))
        self.index += 1
    def pop(self):
        return heapq.heappop(self.heap)[-1]

N = int(input())

favor = [[] for _ in range(N*N)]

room = [[0 for col in range(N)] for row in range(N)]

for i in range(N*N):

    favor[i].extend(list(map(int, stdin.readline().rstrip().split())))

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



def findSeat(li):
    cur = li[0]

    for i in range(N):
        for j in range(N):
            if room[i][j] != 0:
                continue
            emp = 0
            adj = 0
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]

                if 0 <= ny < N and 0 <= nx < N:
                    if li.count(room[ny][nx]) != 0:
                        adj += 1
                    if room[ny][nx] == 0:
                        emp += 1



            seatHeap.push((adj, emp,(i,j)))
    y,x = seatHeap.pop()

    room[y][x] = cur


def countPrice(y,x):
    ans = 0
    for i in favor:
        adj = 0
        if i[0] == room[y][x]:
            for j in range(4):
                ny = y + dy[j]
                nx = x + dx[j]
                if 0 <= ny < N and 0<= nx < N:
                    if i.count(room[ny][nx]) != 0:
                        adj += 1
            break
    if adj == 0:
        return 0
    else:
        ans += 10 ** (adj - 1)
        return ans


for i in favor:
    seatHeap = MyHeap()
    findSeat(i)

ans = 0

for i in range(N):
    for j in range(N):
        ans += countPrice(i,j)

print(ans)

 

 

---

비슷한 문제들