[백준 21608번] 상어 초등학교(파이썬)

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

21608번: 상어 초등학교

 

이 문제는

자리를 배치를 어떻게 해주냐가 관건이었습니다.

그런데 자리를 배치할려고 보면

처음에 어떻게

학생과 학생이 좋아하는 학생을

어떻게 받을 것인가에서 골치를 먹습니다.

저도 이런 류의 문제를 처음 풀 때

특히나 파이썬에 익숙하지 않았을 때는

C에서 어떻게 했지...만 생각하다가

입력부터 막힌 적이 있었습니다.

그러다가 계속 문제를 풀어가면서

'파이썬에서 이렇게 받는구나'

라는 감이 쌓여서

저 부분을 구현했습니다.

저 같은 경우엔

student라는 list에

[[학생 번호][좋아하는 학생들]]

이렇게 받았습니다.

예를들면

[[4],[2,5,1,7]]

이런 식으로요.

그 다음 for 문을 돌 떈

for s in stundet로 하면

s[0]는 4

s[1]은 2,5,1,7이 되는 식으로 나옵니다.

 

그 뒤, 인접자리에 좋아하는 학생이

있는 지 여부를 파악합니다.

인접한 학생이

s[1]에 있는지 여부를 체크해줍니다.

파이썬에서는 간단하게

if ...... in s[1]

이렇게만 해줘도 됩니다.

 

그런데 이 경우가 여러 가지라면

조건2로 넘어갑니다.

조건1에서 구해준 경우들을

차례대로 보면서

0에 얼마나 많이 인접했는가를 체크합니다.

 

그리고 조건1,2,3을 구해주면서

자리 배치를 할 때에마다

s_po에 해당 위치를 넣었습니다.

그 후, 만족도 조사를 할 때

먼저 넣은 것부터 차례대로 불러와서

만족도 조사에 활용했습니다.

 

아래 코드를 보겠습니다.

 

# 백준 21608 상어초등학교
from collections import deque

N = int(input())
student = []
for _ in range(N ** 2):
    num, fav1, fav2, fav3, fav4 = map(int, input().split())
    student.append([num, [fav1, fav2, fav3, fav4]])

# 인접한거 체크할 이동

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

room = [[0] * N for _ in range(N)]

visited = [[False] * N for _ in range(N)]
s_po = deque()

# 자리배치
for s in student:

    # 조건1-->비어있는 칸 중 좋아하는 학생이 인접한 칸에 가장 많은 자리
    max_count = 0
    sort_room = deque()

    for x in range(N):
        for y in range(N):
            if visited[x][y]:
                continue

            tmp_count = 0
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if nx < 0 or nx >= N or ny < 0 or ny >= N:
                    continue
                if room[nx][ny] in s[1]:
                    tmp_count += 1

            if tmp_count > max_count:
                sort_room.clear()
                sort_room.append([x, y])
                max_count = tmp_count
            elif tmp_count == max_count:
                sort_room.append([x, y])

    # sort_room에 하나만 있는 경우는 좋아하는 학생이 인접한 칸이 하나인 경우다
    if len(sort_room) == 1:
        s_x, s_y = sort_room.popleft()
        room[s_x][s_y] = s[0]
        visited[s_x][s_y] = True
        s_po.append([s_x, s_y])
        # print("1")
        # print(s_x,s_y,room[s_x][s_y])
        continue
    # 조건2-->1을 만족하는 게 여러개면, 인접한 칸중에서 비어있는 칸이 가장 많은 칸으로
    # print(sort_room)
    empty_room = deque()
    max_empty = 0
    while sort_room:
        x, y = sort_room.popleft()
        now_empty = 0
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if room[nx][ny] == 0:
                now_empty += 1

        if now_empty > max_empty:
            max_empty = now_empty
            empty_room.clear()
            empty_room.append([x, y])
        elif now_empty == max_empty:
            empty_room.append([x, y])

    # 조건3-->2를 만족하는 칸도 여러개라면, 그 중 행,열이 가장 작은 칸
    # 어처피 2나 3이나, 가장 많은 빈방을 받은 deque에서 가장 왼쪽이 만족하는 답이다
    # 하나면 하나깐 2가 되고
    # 여러개라면 그 중 가장 처음에 넣은 것이니깐 3이 되고

    s_x, s_y = empty_room.popleft()
    room[s_x][s_y] = s[0]
    visited[s_x][s_y] = True
    s_po.append([s_x, s_y])
    # print("2 or 3")
    # print(s_x,s_y,room[s_x][s_y])
    continue

# print(room)
# print(s_po)
# 만족도 조사
sum_good = 0

학생
위치
미리
받고
거기서
만족하는
경우를
세는
경우
for s in student:
    now_count = 0
    x, y = s_po.popleft()
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if nx < 0 or nx >= N or ny < 0 or ny >= N:
            continue
        if room[nx][ny] in s[1]:
            now_count += 1

    if now_count == 0:
        sum_good += 0
    elif now_count == 1:
        sum_good += 1
    elif now_count == 2:
        sum_good += 10
    elif now_count == 3:
        sum_good += 100
    elif now_count == 4:
        sum_good += 1000

print(sum_good)

저는 이 문제를 풀면서

제 나름대로 알고리즘을 구현한 다음

제가 구현한 자리배치가

예시와 맞는지 확인했습니다.

 

만약에 결과값이 맞는지를 확인할 경우

잘못된 코드를 구현하더라도

예시의 결과값이랑 일치할 수도 있습니다.

만약에 '재수없게'

모든 예시랑 결과값이 다 맞았다면

'이거 백퍼 맞음. 제출!'

눌러서 제출했더니

틀렸습니다!

가 나오는...

그럼 풀이하는 입장에서는

'난 분명 다 맞았는데...왜지??'

하면서 헤멜 수 있습니다.

이 문제는 애당초 만족도조사보다

자리배치가 더 큰 문제였기 때문에

자리배치를 구현잘하는 게 킬포인트입니다.

그러니 그걸 제대로 돌아가는지 보는 게

가장 옳바른 확인방법이죠.

 

+++++

개량된 방법입니다.

#백준 21608번 상어초
from collections import deque

N=int(input())

graph=[[0]*N for _ in range(N)]
student=[[]]*(N*N+1)

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

for _ in range(N*N):
    #뒤에 학생들 선호도 조사를 위해 남겨둠.
    data=list(map(int,input().split()))
    good=[data[1] , data[2], data[3], data[4]]
    student[data[0]]=[data[1], data[2] ,data[3] ,data[4] ]
    #1. 비어있는 칸 중 좋아하는 학생이 가장 많은 칸에 배치
    first=deque()
    max_like=0
    for x in range(N):
        for y in range(N):
            if graph[x][y]==0:
                now_like=0
                for d in range(4):
                    nx=x+dx[d]
                    ny=y+dy[d]
                    if nx<0 or nx>=N or ny<0 or ny>=N:
                        continue
                    if graph[nx][ny] in good:
                        now_like+=1
                if max_like<now_like:
                    first.clear()
                    first.append([x,y])
                    max_like=now_like
                elif max_like==now_like:
                    first.append([x,y])
    if len(first)==1:
        px,py=first.pop()
        graph[px][py]=data[0]
    #만족하는 것이 여러가지라면, 비어있는 칸이 가장 많은 걸로 픽
    else:
        max_blank=0
        second=[]
        while first:
            bx,by=first.popleft()
            now_blank=0
            for d in range(4):
                nx=bx+dx[d]
                ny=by+dy[d]

                if nx<0 or nx>=N or ny<0 or ny>=N:
                    continue
                if graph[nx][ny]==0:
                    now_blank+=1
            if max_blank<now_blank:
                second.clear()
                max_blank=now_blank
                second.append([bx,by])
            elif max_blank==now_blank:
                second.append([bx,by])

        second.sort()
        px,py=second.pop(0)
        graph[px][py]=data[0]

#자리배치 후, 만족도 조사를 실시
answer=0

for x in range(N):
    for y in range(N):
        now_on=graph[x][y]
        faver=student[now_on]
        people=0
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if graph[nx][ny] in faver:
                people+=1
        if people>0:
            answer+=10**(people-1)

print(answer)

업그레이드 사항

1. 학생과 학생선호도를 받으면서

바로 자리배치할 수 있게 변경

 

2. 10^(사람수-1)이라는 것을 반영해서

answer에 더하는 것도 간력하게 코드를 변경.

 

3.조건2 3을 구하는 건

deque가 아닌 리스트로 받아서

정렬해주는 방식을 사용.

(이 문제에서는 '굳이 정렬이 필요없다'

손 치더라도

나중에 여러 문제에서는

정렬을 해주는 식으로 조건이 나오곤 합니다.

예를들면

'행중에서 가장 가까운 것, 열중에서 가장 가까운 것 먼저'

이런 식으로 말이죠.

그럴 때는 간단하게 sort한번 사용하면 쉽게 구할 수 있습니다.)