Preview
전형적인 시뮬레이션 문제이다. 때문에 문제에 제시된 조건들을 잘 따져가며 코딩하면 어렵지 않게 해결할 수 있다.
알고리즘
- 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
- 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
- 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
문제에서 제시한대로 만족도 > 빈칸 > 행 > 렬 순의 우선순위로 좌석을 찾아야 한다.
때문에 나의 코드는 다음과 같이 동작한다.
- 학생의 정보를 담은 리스트에서 한명씩 뽑아, 해당하는 학생을 문제의 조건에 맞는 위치에 자리시킨다.
- 위의 내용을 반복하여 모든 학생을 배치시킨 후 N*N행렬을 돌며 각 학생들의 만족도를 result 에 추가한다.
- result 를 출력한다.
함수설명
1. find_seat()
학생의 정보를 입력받아 위의 문제의 조건을 만족시키는 행, 열을 반환하는 함수.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def find_seat(info):
max_count = -1
vacant_count = -1
r,c = 0,0
for i in range(N):
for j in range(N):
if not classroom[i][j]:
cnt, vacant_cnt = check(i,j,info)
if cnt > max_count:
max_count = cnt
vacant_count = vacant_cnt
r,c = i,j
continue
if cnt == max_count:
if vacant_cnt > vacant_count:
vacant_count = vacant_cnt
r,c = i,j
continue
return r,c
2. check()
행,열, 학생의 정보를 입력받아 해당하는 위치 주변의 공석, 좋아하는 사람의 수 를 반환하는 함수.
1
2
3
4
5
6
7
8
9
10
11
12
13
def check(y,x,info):
cnt = 0
vacant_cnt = 0
num, a,b,c,d = info
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if 0 <= ny < N and 0 <= nx < N:
if not classroom[ny][nx]:
vacant_cnt += 1
if classroom[ny][nx] == a or classroom[ny][nx] == b or classroom[ny][nx] == c or classroom[ny][nx] == d:
cnt += 1
return cnt, vacant_cnt
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import sys
input = sys.stdin.readline
dy = [-1,0,1,0]
dx = [0,1,0,-1]
def check(y,x,info):
cnt = 0
vacant_cnt = 0
num, a,b,c,d = info
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if 0 <= ny < N and 0 <= nx < N:
if not classroom[ny][nx]:
vacant_cnt += 1
if classroom[ny][nx] == a or classroom[ny][nx] == b or classroom[ny][nx] == c or classroom[ny][nx] == d:
cnt += 1
return cnt, vacant_cnt
def find_seat(info):
max_count = -1
vacant_count = -1
r,c = 0,0
for i in range(N):
for j in range(N):
if not classroom[i][j]:
cnt, vacant_cnt = check(i,j,info)
if cnt > max_count:
max_count = cnt
vacant_count = vacant_cnt
r,c = i,j
continue
if cnt == max_count:
if vacant_cnt > vacant_count:
vacant_count = vacant_cnt
r,c = i,j
continue
return r,c
N = int(input())
likes = [0] * (N*N)
classroom = [ [0] * N for _ in range(N)]
counts = [ [0] * N for _ in range(N)]
for i in range(N*N):
s_num, a, b, c, d = map(int,input().split())
likes[i] = (s_num,a,b,c,d)
for info in likes:
r,c = find_seat(info)
classroom[r][c] = info[0]
counts[r][c] = [ item for item in info[1:]]
result = 0
for i in range(N):
for j in range(N):
count = 0
a,b,c,d = counts[i][j]
for k in range(4):
ny = i + dy[k]
nx = j + dx[k]
if 0<= ny < N and 0 <= nx < N:
if classroom[ny][nx] == a or classroom[ny][nx] == b or classroom[ny][nx] == c or classroom[ny][nx] == d:
count += 1
if count > 0:
result += 10 ** (count - 1)
print(result)
결과
