문제 링크 : https://www.acmicpc.net/problem/21608
1. 접근 방법
구현의 난이도가 낮지는 않지만, 조건 분기가 많지 않아서 비교적 어렵지 않게 구현할 수 있을 것이라 생각한다.
구현 문제는 문제만 잘 읽는다면, 한 번에 해결할 수도 있는 문제 종류라고 생각한다.
2. 풀이 코드
🖥python 코드
import sys
input = sys.stdin.readline
def search_friends(student: int, friends: list):
global students_order, students_seat, classroom
# 친구들의 자리가 이미 정해져있는지
prob_seat = []
for f in friends:
# 친구가 이미 자리 차지하고 있을 때
if students_seat[f] != []:
x, y = students_seat[f]
# 4방향 탐색
if x > 0 and classroom[x - 1][y] == 0:
prob_seat.append((x - 1, y))
if x < n - 1 and classroom[x + 1][y] == 0:
prob_seat.append((x + 1, y))
if y > 0 and classroom[x][y -1 ] == 0:
prob_seat.append((x, y - 1))
if y < n - 1 and classroom[x][y + 1] == 0:
prob_seat.append((x, y + 1))
return prob_seat
def search_empty_seat():
global n, classroom
# 비어있는 자리중 가능성 있는 자리 탐색
prob_seat = []
empty_near = 0
for i in range(n):
for j in range(n):
if classroom[i][j] == 0:
empty = 0
# 4방향 탐색
if i > 0 and classroom[i - 1][j] == 0:
empty += 1
if i < n - 1 and classroom[i + 1][j] == 0:
empty += 1
if j > 0 and classroom[i][j -1 ] == 0:
empty += 1
if j < n - 1 and classroom[i][j + 1] == 0:
empty += 1
if empty == 4:
return i, j
elif prob_seat == []:
empty_near = empty
prob_seat = [i, j]
elif empty > empty_near:
empty_near = empty
prob_seat = [i, j]
return prob_seat
def find_best_seat(prob_seat):
global n, classroom
# 가능한 자리 중 조건에 맞는 최적 자리
seat = []
friends_count = 0
empty_near = 0
for i in range(len(prob_seat)):
friends_near = 0
for j in range(i, len(prob_seat)):
if prob_seat[i] == prob_seat[j]:
friends_near += 1
# 다른 자리보다 친구 수가 주변에 적으면
if friends_near < friends_count:
continue
# 주변 빈자리 탐색
x, y = prob_seat[i]
empty = 0
# 4방향 탐색
if x > 0 and classroom[x - 1][y] == 0:
empty += 1
if x < n - 1 and classroom[x + 1][y] == 0:
empty += 1
if y > 0 and classroom[x][y -1 ] == 0:
empty += 1
if y < n - 1 and classroom[x][y + 1] == 0:
empty += 1
# 아직 자리가 비어있을 때
if seat == []:
seat = x, y
friends_count = friends_near
empty_near = empty
# 다른 자리보다 친구 수가 더 많으면 변경
if friends_near > friends_count:
friends_count = friends_near
seat = [x, y]
empty_near = empty
# 친구수가 같다면, 비어 있는 칸 확인
else:
# 주변 빈자리가 더 많다면 교체
if empty > empty_near:
seat = [x, y]
empty_near = empty
# 주변 빈 자리가 같으면 더 왼쪽 더 위쪽 일때 교체
elif empty == empty_near:
if x < seat[0] or (x == seat[0] and y < seat[1]):
seat = [x, y]
return seat
def count_happiness(classroom) -> int:
global students_order, students_seat
happiness = 0
for student, *friends in students_order:
# 인접 자리 친구
friends_near_count = 0
student_pos = students_seat[student]
for f in friends:
if abs(student_pos[0] - students_seat[f][0]) + abs(student_pos[1] - students_seat[f][1]) == 1:
friends_near_count += 1
# 인접 친구 수에 따라 점수 부여
if friends_near_count == 1:
happiness += 1
elif friends_near_count == 2:
happiness += 10
elif friends_near_count == 3:
happiness += 100
elif friends_near_count == 4:
happiness += 1000
return happiness
n = int(input())
# 학생 자리 배치 순서
students_order = [tuple(map(int, input().split())) for _ in range(n ** 2)]
# 각 학생의 자리
students_seat = [[] for _ in range(n ** 2 + 1)]
# 교실
classroom = [[0] * n for _ in range(n)]
# 첫 학생부터 자리 채우기
for student, *friends in students_order:
# 친구들 기준 가능한 자리가 있는지
prob_seat = search_friends(student, friends)
# 친구들 기준 가능한 자리 없을 때
if prob_seat == []:
# 빈 자리중 가능한 빈자리 탐색
x, y = search_empty_seat()
classroom[x][y] = student
students_seat[student] = [x, y]
# 친구들 기준 가능한 자리 있을 때
else:
# 받은 가능한 자리 중 최선의 자리 선택
x, y = find_best_seat(prob_seat)
classroom[x][y] = student
students_seat[student] = [x, y]
print(count_happiness(classroom))
📕풀이 과정
가장 밑 for문을 실행하기 전 모든 입력을 받고 준비한다.
문제에서 지시한것처럼 각 학생에 대하여 어느 자리에 지정할지 탐색한다.
탐색은 크게 3가지 과정(함수)로 해결했는데
1. search_friends : 우선 친구들이 앉아 있는지 확인
2. serch_empty_seat : 친구들이 앉아 있지 않거나, 친구들 주변 빈자리가 없을 때, 빈자리 중 선택
3. find_best_seat : 앉아있는 친구들 주변 자리 중 최선의 자리 선택
하는 과정으로 최적의 자리를 찾아 해당 자리에 학생을 두는 방식으로 진행햇다.
마지막 행복도는 문제에서 주어진 방식으로 간단하게 계산했다.
3. 생각 정리
하드 코딩을 한 부분이 많다. 그러다 보니 4방향 탐색하는 부분 코드가 거의 겹치게 여러 번 등장하게 되는데, 이 부분을 압축하지 못한 것은 아쉽지만, 한편으로는 이 부분 때문에 더욱 빠르게 실행되었는 게 아닐까 생각한다.
예전에는 구현 문제가 마냥 어렵게 느껴졌는데, 다양한 문제를 해결하며 얻은 팁을 적자면, 내가 마지막에 for문을 구성하여 해결한 것처럼 특정 반복할 작업을 미리 구축하고, 해당 작업을 할 함수를 작성하는 방식으로 해결한다면, 이러한 구현 문제 해결에 큰 도움이 될 것이라 생각한다.
'CS > 알고리즘 & 문제풀이' 카테고리의 다른 글
[Python] 백준 20056 마법사 상어와 파이어볼 (0) | 2021.10.25 |
---|---|
[Python] 소가 길을 건나간 이유 7 (0) | 2021.10.25 |
[Python] 백준 16926 / 16927 배열 돌리기 1, 2 (0) | 2021.10.12 |
[Python] 백준 10835 카드게임 (0) | 2021.10.10 |
[Python] 백준 1398 동전 문제 (0) | 2021.10.08 |
댓글