[CT]놀이기구 탑승

1. 문제

• 놀이기구 : n * n

  

• 학생 : n * n 명

  • 각 학생별로 좋아하는 학생 4명씩 (동일한 학생에 대해 좋아하는 학생 번호 중복 가능
  • 입력으로 주어진 학생들의 순서대로 다음 조건에 따라 가장 우선순위가 높은 칸으로 탑승 ( 항상 비어있는 칸으로만 이동)

    1. 격자를 벗어나지 않는 4방향으로 인접한 칸 중 앉아있는 좋아하는 친구의 수가 가장 많은 위치로

    2. 1번 조건을 만족하는 칸이 여러 곳이라면 인접한 칸 중 비어있는 칸의 수가 가장 많은 위치로

    3. 2번 조건을 만족하는 칸이 여러 곳이라면 행 번호가 가장 작은 위치로

    4. 3번 조건을 만족하는 칸이 여러 곳이라면 열 번호가 가장 작은 위치로

       
  • 최종 점수 계산
    • 각 학생의 인접한 곳에 앉아있는 좋아하는 친구의 수

⇒ 들어오는 학생의 순서와 각 학생마다 좋아하는 4명의 학생 번호가 주어졌을 때, 최종 점수?

2. 풀이

• like_info : 입력으로 주어진 학생-좋아하는 친구에 대한 리스트
• ride : n * n 크기의 놀이기구 탑승 공간
• 자리에 앉는 기준 : 주변에 좋아하는 친구 수 > 빈칸 수 > 행 번호 > 열 번호
• like_info를 한 행씩 읽으면서, 각 학생이 앉을 자리를 탐색
  • ride의 각 칸마다 탐색하며 candidates 리스트를 채우기
    • 칸이 비어 있다면 해당 칸 위, 아래, 왼쪽, 오른쪽 탐색하며 빈칸 수와 좋아하는 학생의 수를 확인함
    • (좋아하는 친구 수, 탐색한 빈칸 수, 행번호, 열번호) 를 candidates리스트에 넣음
    • candidates를 정렬한 뒤 맨 첫번째 원소에 해당되는 위치에 학생 정보 입력

3. 코드

def look_around(r, c, favorites):
    fav, blanks = 0, 0
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        
        if 0 <= nr < n and 0 <= nc < n:
            if ride[nr][nc] in favorites:
                fav += 1
            elif ride[nr][nc] == 0:
                blanks += 1
    return fav, blanks
        
n = int(input())
like_info = [ list(map(int, input().split())) for _ in range(n*n) ]

ride = [ [0]*(n) for _ in range(n)]

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

for i in range(n * n):
    student = like_info[i][0]
    favorites = like_info[i][1:]
    
    candidates = []
    
    for r in range(n):
        for c in range(n):
            
            if ride[r][c] == 0:
                fav, blanks = look_around(r, c, favorites)
                candidates.append([fav, blanks, r, c])
                
    candidates.sort(key= lambda x: (-x[0], -x[1], x[2], x[3]))
    seat = candidates[0]
    ride[seat[2]][seat[3]] = student

students = [x[0] for x in like_info]

answer = 0
for i in range(n):
    for j in range(n):
        student_idx = students.index(ride[i][j])
        fav, blanks = look_around(i, j, like_info[student_idx][1:])
        if fav > 0:
            answer += 10 ** (fav - 1)
print(answer)

+α