BOJ 21608 - 상어 초등학교

BOJ 21608 - 상어 초등학교

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

이번 문제는 구현할 기능이 세 가지나 있는 문제입니다.

문제에서 인접한 자리는 상하좌우로만 된다고 나와 있습니다.

이번에는 4개로 나누어서 문제를 풀어보겠습니다.

1. 입력값 받기

2. 비어있는 칸 중에서 좋아하는 사람이 가장 많이 인접한 칸 찾기

3. 빈칸이 가장 많이 인접한 칸 찾기

4. 점수 계산

1. 입력값 받기

우리는 N x N 배열도 필요하므로 모든 값이 0인 배열 arr을 만들어주고, 입력값을 받아주면 됩니다.

여기서 N*N줄을 입력받을 때, 학생의 번호와 좋아하는 학생들을 딕셔너리로 저장하면 편합니다.

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

2. 좋아하는 학생이 가장 많이 인접한 칸

빈칸에서 좋아하는 학생이 가장 많이 인접한 칸을 찾아주면 됩니다.

우리는 좋아하는 학생이 가장 많이 인접한 칸이 여러 개일 수도 있으므로 love라는 리스트를 하나 만들어서 [인접한 좋아하는 학생 수, 좌표를 넣어줄 큐] 형태로 저장을 해야 합니다.

from collections import deque

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

for t in range(n*n):
    love = [0, deque()]

그래서 위와 같이 collections.deque를 불러오고, 첫 번째 단계는 love라고 해서 초기값은 [ 0, deque() ]로 만들어줍니다.

그리고 이제 (0, 0)에서 (n-1, n-1)중에 빈칸만 확인해서 초깃값을 업데이트하면 됩니다.

예를 들어서 love = [ 2, deque([(0, 0), (1, 2)])] 로 되어 있으면 현재 좋아하는 사람이 가장 인접된 수는 2이고, 그 칸은 (0, 0)과 (1, 2)가 있다는 뜻입니다. 만약 (3, 4)에서 좋아하는 사람이 가장 인접된 수가 3명이 된다면 love = [ 3, deque([(3,4)])] 가 됩니다.

이번 문제에는 상하좌우가 필요하므로 dx, dy 를 만들어줍니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

for t in student.keys():
    love = [0, deque()]

그리고 상하좌우 인접한 자리를 확인할 때, 배열의 범위가 넘어가지 않는지 확인해야 하므로 범위 내에 있으면 True, 아니면 False를 반환하는 check 함수를 만들어주면 됩니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n: return True
    return False

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

for t in student.keys():
    love = [0, deque()]

이제 for문을 돌려서 빈칸에서 좋아하는 사람이 가장 많이 인접한 칸을 찾으면 됩니다.

주의할 점

본문 세 번째 조건에서는 자리가 여러 개라면 1순위는 행의 번호가 가장 작은 칸을, 2순위는 열의 번호가 가장 작은 칸을 선택해야 합니다.

그래서 이건 정렬을 해야 한다고 생각할 수 있겠지만, 아래와 같이 탐색하게 되면 정렬을 하지 않아도 무조건 행의 번호가 작은 순, 행의 번호가 같으면 열의 번호가 작은 순으로 정렬될 수 있다는 것을 알 수 있습니다.

for i in range(n):
    for j in range(n):
        blah blah

def check(x, y):
    if 0 <= x < n and 0 <= y < n: return True
    return False

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

for t in student.keys():
    love = [0, deque()]
    for x in range(n):
        for y in range(n):
            if arr[x][y] == 0:
                val = 0
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if check(nx, ny) and arr[nx][ny] in student[t]: val += 1

위와 같은 코드처럼 빈칸(if arr[x][y] == 0)일 때, (x, y)를 (nx, ny)로 만들어서 범위 내에 있는지 확인 후에 좋아하는 학생들 목록에 arr[nx][ny]가 들어가는지 확인해주면 됩니다. 들어가 있으면 val += 1을 해주고, 아니면 그냥 넘어가면 됩니다.

그리고 이제 val이 love[0]과 같으면 큐에 좌표를 넣어주고, val > love[0]이면 love = [ val, deque([(좌표)])]로 새로 만들어주면 됩니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n: return True
    return False

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

for t in student.keys():
    # 좋아하는 학생이 가장 많이 인접한 칸 찾기
    love = [0, deque()]
    for x in range(n):
        for y in range(n):
            if arr[x][y] == 0:
                val = 0
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
                if val == love[0]: love[1].append((x,y))
                if val > love[0]: love = [val, deque([(x,y)])]

이렇게 해서 첫 번째 조건을 완료하였습니다.

이제 큐에 들어 있는 원소의 개수가 2개 이상이면 두 번째 조건으로 넘어가고, 1개이면 바로 자리를 배정하면 됩니다.

그런데 어차피 원소의 개수가 1개이면, 두 번째 조건을 돌려도 원소가 1개만 있으므로 저 값으로 결정하게 됩니다.

그래서 저는 if문 없이 그냥 코드를 추가하겠습니다.

if len(love[1]) == 1:
    x, y = love[1].popleft()
    arr[x][y] = student[t][0]
    continue

원소의 개수가 1개일 때의 바로 자리를 배정해주는 조건문을 추가하고 싶은 분은 위 코드를 넣어주시면 됩니다.

3. 빈칸이 가장 많이 인접한 칸 찾기

이제 love[1]의 큐를 가지고 빈칸이 가장 많이 인접한 칸을 찾아주면 됩니다.

이번에는 blank라는 리스트에 값을 저장하는데, blank의 값은 [빈칸이 가장 많이 있는 개수, 좌표들을 저장할 리스트] 로 만들어주면 됩니다.

첫 번째 조건과는 다르게 큐가 아닌 리스트로 저장해주는 이유는 굳이 큐를 사용할 필요는 없기 때문입니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n: return True
    return False

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

for t in student.keys():
    # 좋아하는 학생이 가장 많이 인접한 칸 찾기
    love = [0, deque()]
    for x in range(n):
        for y in range(n):
            if arr[x][y] == 0:
                val = 0
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
                if val == love[0]: love[1].append((x,y))
                if val > love[0]: love = [val, deque([(x,y)])]
    # 빈칸이 가장 많은 자리 찾기
    blank = [0, []]

이번엔 큐에서 원소를 빼서 확인하므로 while문을 이용하여 blank에 값을 넣어주면 됩니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n: return True
    return False

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

for t in student.keys():
    # 좋아하는 학생이 가장 많이 인접한 칸 찾기
    love = [0, deque()]
    for x in range(n):
        for y in range(n):
            if arr[x][y] == 0:
                val = 0
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
                if val == love[0]: love[1].append((x,y))
                if val > love[0]: love = [val, deque([(x,y)])]
    # 빈칸이 가장 많은 자리 찾기
    blank = [0, []]
    while love[1]:
        x, y = love[1].popleft()
        val = 0
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if check(nx, ny) and arr[nx][ny] == 0:
                val += 1

val의 값이 blank[0]과 같으면 blank[1]에 좌표를 추가해주고, val > blank[0]이면 blank = [val, [좌표]]로 수정해주면 됩니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n: return True
    return False

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

for t in student.keys():
    # 좋아하는 학생이 가장 많이 인접한 칸 찾기
    love = [0, deque()]
    for x in range(n):
        for y in range(n):
            if arr[x][y] == 0:
                val = 0
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
                if val == love[0]: love[1].append((x,y))
                if val > love[0]: love = [val, deque([(x,y)])]
    # 빈칸이 가장 많은 자리 찾기
    blank = [0, []]
    while love[1]:
        x, y = love[1].popleft()
        val = 0
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if check(nx, ny) and arr[nx][ny] == 0:
                val += 1
        if val == blank[0]: blank[1].append((x,y))
        if val > blank[0]: blank = [val, deque([(x,y)])]

이제 blank[1]에 있는 첫 번째 값은 무조건 본문 1, 2 조건을 만족하면서 행의 번호와 열의 번호가 가장 작은 좌표입니다.

그래서 blank[1]의 첫 번째 값 좌표에 t번째 학생의 번호인 student[t][0]을 저장하면 되겠습니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n: return True
    return False

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

for t in student.keys():
    # 좋아하는 학생이 가장 많이 인접한 칸 찾기
    love = [0, deque()]
    for x in range(n):
        for y in range(n):
            if arr[x][y] == 0:
                val = 0
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
                if val == love[0]: love[1].append((x,y))
                if val > love[0]: love = [val, deque([(x,y)])]
    # 빈칸이 가장 많은 자리 찾기
    blank = [0, []]
    while love[1]:
        x, y = love[1].popleft()
        val = 0
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if check(nx, ny) and arr[nx][ny] == 0:
                val += 1
        if val == blank[0]: blank[1].append((x,y))
        if val > blank[0]: blank = [val, deque([(x,y)])]
    # 좌석 배정 
    x, y = blank[0]
    arr[x][y] = t

4. 점수 계산하기

이제 좌석을 다 배정했으면 점수를 더해주면 됩니다. 본문에 있는 점수 배점대로 score라는 배열을 만들어서 score = [0, 1, 10, 100, 1000]을 만들어주고, 인접하고 있는 좋아하는 학생 수대로 ans에 점수를 더해주면 됩니다.

그리고 ans를 출력하면 끝나게 됩니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n: return True
    return False

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

for t in student.keys():
    # 좋아하는 학생이 가장 많이 인접한 칸 찾기
    love = [0, deque()]
    for x in range(n):
        for y in range(n):
            if arr[x][y] == 0:
                val = 0
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
                if val == love[0]: love[1].append((x,y))
                if val > love[0]: love = [val, deque([(x,y)])]
    # 빈칸이 가장 많은 자리 찾기
    blank = [0, []]
    while love[1]:
        x, y = love[1].popleft()
        val = 0
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if check(nx, ny) and arr[nx][ny] == 0:
                val += 1
        if val == blank[0]: blank[1].append((x,y))
        if val > blank[0]: blank = [val, [(x,y)]]
    x, y = blank[1][0]
    arr[x][y] = t
# 점수 구하기
ans = 0
score = [0, 1, 10, 100, 1000]
for x in range(n):
    for y in  range(n):
        val = 0
        for i in range(4):
            nx, ny = x+dx[i],y+dy[i]
            if check(nx, ny) and arr[nx][ny] in student[arr[x][y]]: val += 1
        ans += score[val]
print(ans)

다른 방법

조건 1과 조건 2를 합쳐서 만들 수도 있습니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n: return True
    return False

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

n = int(input())
arr = [[0]* n for _ in range(n)]

student = {}
for i in range(n*n):
    x, s1, s2, s3, s4 = map(int,input().split())
    student[x] = [s1, s2, s3, s4]

for t in student.keys():
    # 좋아하는 학생이 가장 많이 인접한 칸이면서 빈칸이 많은 칸 찾기
    best = [0, 0, []] # 좋아하는 학생 수, 빈칸의 수, 좌표
    for x in range(n):
        for y in range(n):
            if arr[x][y] == 0:
                love = 0
                zero = 0
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if check(nx, ny):
                        if arr[nx][ny] in student[t]: love += 1
                        if arr[nx][ny] == 0: zero += 1
                if love == best[0] and zero == best[1]: best[2].append((x,y))
                if love > best[0] or (love == best[0] and zero > best[1]):
                    best = [love, zero, [(x,y)]]
    x, y = best[2][0]
    arr[x][y] = t
# 점수 구하기
ans = 0
score = [0, 1, 10, 100, 1000]
for x in range(n):
    for y in  range(n):
        val = 0
        for i in range(4):
            nx, ny = x+dx[i],y+dy[i]
            if check(nx, ny) and arr[nx][ny] in student[arr[x][y]]: val += 1
        ans += score[val]
print(ans)