[문제풀이-백준] 21608. 상어초등학교

풀이

구현

아이디어

• 학생별 좋아하는 사람을 딕셔너리 형태로 저장

• 인접칸 조사할 때, 우선순위를 이용하기 위해 리스트 소팅 사용

  1. 좋아하는 사람의 수
  2. 비어있는 칸의 수
  3. 행 번호 작은 순
  4. 열 번호 작은 순

  => 리스트에 묶어서 한번에 넣기

  => 나중에 한번 소팅

• 후보 리스트(cand)의 맨 앞에 있는 요소가 최종 배치 받은 자리가 된다.

• 매번 이중 for문을 돌면서 빈자리를 찾으면 비효율적이다. 따라서 visit은 딕셔너리를 이용하고 배치 받은 자리는 visit에서 제거

• 만족도 조사를 위해 다시 이중 for문을 돌면서 탐색한다.

  • 미리 좋아하는 학생 수를 넣어놓으려고 했으나, 나중에 인접 칸에 좋아하는 학생이 올 경우 그 학생은 셀 수 없다. 따라서 모든 학생의 자리배치가 끝나고 다시 탐색해야한다. 문제의 맨 밑에 나와있는 조건이다.
  • 좋아하는 학생의 수가 0을 제외한 나머지 수는 10의 거듭제곱(학생 수 - 1)의 규칙이 있다.

시간 복잡도

O(n^4)이지만 n이 최대 20이므로 통과할 수 있다.

코드

# 20:17~21:08
direct = [(-1,0), (0,1), (1,0), (0,-1)]
Y, X, DIRECTION = 0, 1, 4
N = int(input())
student_info = {}
total_student = N ** 2
for _ in range(total_student):
    information = list(map(int,input().split()))
    student_info[information[0]] = information[1:]

placement = [[0]*N for _ in range(N)]
visit = {(i,j): True for i in range(N) for j in range(N)}
for student, info in student_info.items():
    cand = []
    for y, x in visit.keys():
        like, blank = 0, 0
        for dir in range(DIRECTION):
            ny, nx = y + direct[dir][Y], x + direct[dir][X]
            if 0 <= ny < N and 0 <= nx < N:
                if placement[ny][nx] and placement[ny][nx] in info: like += 1
                elif not placement[ny][nx]: blank += 1
        cand.append([-like, -blank, y, x])
    cand = sorted(cand)
    like, blank, y, x = cand[0]
    placement[y][x] = student
    visit.pop((y,x))

answer = 0
for y in range(N):
    for x in range(N):
        student = placement[y][x]
        like_cnt = 0
        for dir in range(DIRECTION):
            ny, nx = y + direct[dir][Y], x + direct[dir][X]
            if 0 <= ny < N and 0 <= nx < N and placement[ny][nx] and placement[ny][nx] in student_info[student]:
                like_cnt += 1
        if like_cnt:
            answer += 10**(like_cnt-1)
print(answer)