[221001] 백준 21608 : 상어 초등학교

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

21608번: 상어 초등학교

1. 연습장 없이 눈으로 풀어보자

 눈으로만 읽고 풀려니까 잘 안 읽힌다.. 조건을 잘 살펴보자

 

|r1 - r2| + |c1 - c2| = 1 ?

 

위의 식은 상, 하, 좌, 우 탐색하라는 이야기이다. 그렇다면 굳이 저 식을 사용하지 않아도 된다.

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

 나는 위의 내용을 다음과 같이 정리해서 코드를 짰다.

 

1.  학생 한 명을 선택, 보드판의 위치를 고른다. 이때, 고른 보드판에는 학생이 없어야 한다.
2.  인접한 칸에 해당 학생이 좋아하는 학생이 있는지 세서 딕셔너리에 집어넣는다. 

• 이 때 좋아하는 학생의 최대 수가 4명이니까 4부터 0명까지 거꾸로 반복문을 돌리면서 딕셔너리의 크기를 탐색한다.
• 만약에 딕셔너리 인덱싱 한 배열의 크기가 1이면 학생을 배치하고 끝.
• 그렇지 않다면 내부 리스트의 좌표점에 대해서 비어있는 공간이 몇 개인지 탐색해서 다시 정리 및 결정

 

이렇게 하면 1, 2, 3번의 조건 흐름에 맞게 코드를 짤 수 있다. 좋아하는 친구가 없는 경우에 대해서도 딕셔너리에 들어가기 때문에 작동하는데 문제가 없다.

2. 전체 코드

메모리 : 116484 KB, 시간 : 220 ms, 풀이 시간 : 90 min

※ 객기 부리지 말고 종이에 쓰면서 풀자...

N = int(input())
info_dict = {}
order_list = []
board = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N**2):
    tmp = list(map(int, input().split()))
    info_dict[tmp[0]] = tmp[1:]
    order_list.append(tmp[0])

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

def search(ns):
    # 0 : like_cnt, 1 : empty_cnt
    like_info = {0 : [], 1: [], 2:[], 3:[], 4:[]}
    empty_info = {0 : [], 1: [], 2:[], 3:[], 4:[]}
    for i in range(N):
        for j in range(N):
            x, y = i, j
            if board[x][y] != 0 : continue
            like_cnt = 0
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if 0 <= nx < N and 0 <= ny < N :
                    if board[nx][ny] in info_dict[ns] : like_cnt += 1
            like_info[like_cnt].append([x, y])
    for k in range(4, -1, -1):
        if len(like_info[k]) == 1 :
            x, y = like_info[k][0]
            board[x][y] = ns
            break
        elif len(like_info[k]) > 1 :
            like_info[k].sort()
            for it in range(len(like_info[k])):
                x, y = like_info[k][it]
                empty_cnt = 0
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if 0 <= nx < N and 0 <= ny < N :
                        if board[nx][ny] == 0 : empty_cnt += 1
                empty_info[empty_cnt].append([x, y])
            for empty in range(4, -1, -1):
                if empty_info[empty] :
                    empty_info[empty].sort()
                    x, y = empty_info[empty][0]
                    board[x][y] = ns
                    break
            break
def scoring():
    global score
    s_list = [0, 1, 10, 100, 1000]
    for i in range(N):
        for j in range(N):
            x, y = i, j
            student = board[x][y]
            cnt = 0
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if 0 <= nx < N and 0 <= ny < N :
                    if board[nx][ny] in info_dict[student] : cnt += 1
            score += s_list[cnt]

def solve():
    for st in range(N**2):
        search(order_list[st])
    scoring()

score = 0
solve()
print(score)