[Python] BOJ 21608 - 상어 초등학교

# 이번 2021년 삼성SW역량테스트 오전 기출문제이다.

   최근 몇년간 문제들을 보면 삼성은 상어를 너무 좋아하는거같다 ㅋㅋㅋ

   (아기상어, 청소년 상어, 상어 초등학교 등등..)

# 지겹도록 나오는 구현, 시뮬레이션 문제이다. (BFS를 곁들인)

 

1. 우선 student_list라는 딕셔너리에 좋아하는 학생들의 번호를 넣어준다.

2. 40번째 줄부터 studnet_list에 있는 학생 순서대로 시뮬레이션을 돌려준다.

3. m에 모든 학생 자리배치를 완료한 뒤 happy함수로 만족도를 구해서 출력한다.

 

# first_check함수는 bfs로 그래프를 탐색하듯이 상하좌우를 탐색하며 (nx, ny)가 맵을 벗어나지 않고

   m[nx][ny]가 student_list[st]에 존재하면(좋아하는 학생이 인접한 칸에 있는 경우)

   cnt를 1증가시킨다.

 

# second_check함수는 똑같이 상하좌우를 탐색하며 (nx, ny)가 맵을 벗어나지 않고 m[nx][ny] == 0이면

   (비어있는 칸이면) cnt를 1증가시킨다.

 

# 코드 주석은 주석 아래줄을 설명한 것

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
m = [[0] * N**2 for _ in range(N**2)]
student_list = defaultdict(list)
for _ in range(N**2):
	student, *s = map(int,input().split())
	student_list[student] = s
dx, dy = [0,0,-1,1], [-1,1,0,0]

# 1번조건 check
def first_check(i, j, st):
	cnt = 0
	for x in range(4):
		nx, ny = i + dx[x], j + dy[x]
		if 0 <= nx < N and 0 <= ny < N and m[nx][ny] in student_list[st]:
			cnt += 1
	return cnt

# 2번조건 check
def second_check(i, j):
	cnt = 0
	for x in range(4):
		nx, ny = i + dx[x], j + dy[x]
		if 0 <= nx < N and 0 <= ny < N and m[nx][ny] == 0:
			cnt += 1
	return cnt

# 만족도 구하는 함수
def happy(i, j):
	cnt = 0
	happy_cnt = [0,1,10,100,1000]
	for x in range(4):
		nx, ny = i + dx[x], j + dy[x]
		if 0 <= nx < N and 0 <= ny < N and m[nx][ny] in student_list[m[i][j]]:
			cnt += 1
	return happy_cnt[cnt]

for st in student_list:
	dic = defaultdict(list)
	for i in range(N):
		for j in range(N):
			if m[i][j] == 0:
				dic[first_check(i, j, st)].append((i, j))
    	# dic의 key순으로 내림차순 정렬 -> 좋아하는 학생이 많은 칸 순서대로 정렬됨
	s = sorted(dic.items(), key = lambda x: -x[0])
    	# 1번 조건만족하는 칸이 여러개이면 2번조건으로 넘어감
	if len(dic[s[0][0]]) > 1:
		dic2 = defaultdict(list)
		for i,j in dic[s[0][0]]:
			dic2[second_check(i, j)].append((i, j))
        	# dic2의 key순으로 내림차순 정렬 -> 비어있는 칸이 많은 순서대로 정렬됨
		s = sorted(dic2.items(), key = lambda x: -x[0])
        	# 2번 조건 만족하든 안하든 좌표가 (0, 0) 부터 정렬되어있으므로 첫번째 좌표에 st넣어줌
		m[dic2[s[0][0]][0][0]][dic2[s[0][0]][0][1]] = st
	else:
		m[dic[s[0][0]][0][0]][dic[s[0][0]][0][1]] = st

dab = 0
for i in range(N):
	for j in range(N):
		dab += happy(i, j)
print(dab)

(solved.ac 티어: 실버 1)

 

# 제출하고보니 first_check함수와 second_check함수가 bfs도는 구조도 같고 범위도 같아서 그냥 

   두 함수를 합치고 40번째 줄부터 자리배치하는 코드도 뭔가 dic[s[0][0]][0][0] 이런식으로

   너무 보기 안 좋아서 줄일 수 있었다. 최적화를 한 코드는 다른 분들의 코드를 참고하면 

   될 것 같아서 나는 그냥 처음에 짠 코드로 포스팅을 했다. (수행시간도 더 짧게 걸림)

 

# 예제도 다 맞고 해서 제출했는데, 계속 '틀렸습니다'가 떠서 며칠동안 고민하고 노가다를 뛰며

   고생했지만, 알고보니 구현이 틀린게 아니라 N의 범위가 틀린거였다..

   (N이 항상 3인줄 알고 m크기가 3x3인 상태로 계속 시뮬레이션을 돌렸다)

   진짜 어이가 없고 화가났다 ㅋㅋㅋ

   문제 좀 잘 읽자..