문제
문제가 너무 길고 복잡하다 ! 미래에 까먹을 나를 위해 링크를 남기도록 하지
요약하면, 세 조건이 핵심이다.
- 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
- 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
- 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
알고리즘 종류 ) 구현 알고리즘
아직 초보자라서 알고리즘 종류를 보고 힌트를 얻어서 푸는 편이다. 이 문제는 구현 알고리즘이라고 되어있는데 그 뜻을 몰라서 헤맸다. bfs, dfs 로 최대한 풀려다가 도저히 안 되어서 확인해본 결과, 구현 알고리즘은 ‘구현이란 ‘머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정’이라고 할 수 있다. 따라서, 사실 특정한 ‘구현’ 알고리즘이 있는 것은 아니고, 모든 알고리즘 문제가 구현의 문제라고 할 수 있다.’ 라고 한다. 완전 탐색 등, 알고리즘 자체는 어렵지 않으나 구현 자체가 복잡한 문제들을 이렇게 부르는 것 같다. 문제에서 데이터 크기 제한을 많이 빡세게 주지 않는 경우 주로 완전 탐색을 이용한 구현 알고리즘인 것 같다. 이 문제에서도 제한은 3<=N<=20 으로 널널했다. 하지만 ㅋㅋㅋㅋㅋ 나는 꼼꼼하게 조건만 다 넣어주면 되는 것을 계속 뭐 하나를 빠뜨려서 겁나 디버깅해야만 했다.
풀이 & 코드 & 용어
👯♂️ 나와 인접한 친구들 자리 (=인접한 칸) ; 내 바로 앞, 내 양 옆,내 바로 뒤의 경우 해당
우선 교실 전체의 좌석을 cell (교실)에, 각 자리의 인접한 친구들 자리가 얼마나 비었는지를 empty 에 초기화해준다.
문제에서 제공하는 test case 예시대로 총 9명이라고 하면
아무도 안 앚은 빈 cell 은
이러하다.
그리고 각 자리마다 나와 인접한 친구들 자리가 얼마나 비어있는지를 나타내는 empty 도
이렇게 초기화시켜준다.
import sys
input=sys.stdin.readline
class Sclass:
def read(self):
self.n=int(input())
self.info=[list(map(int,input().split())) for _ in range(self.n**2)]
self.cell=[[0]*self.n for i in range(self.n)]
self.empty=[[3]*self.n for i in range(self.n)]
self.empty[0][0]=2
self.empty[0][self.n-1]=2
self.empty[self.n-1][0]=2
self.empty[self.n-1][self.n-1]=2
for p in range(self.n):
for q in range(self.n):
if p>0 and q>0:
if p<self.n-1 and q<self.n-1:
self.empty[p][q]=4
에서 맨 처음 4번의 경우, 어차피 교실에는 아무도 안 앉아있을 것이므로 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 에 해당하는 자리가 딱히 없다. = 2번 조건이 없다면 아무 데나 앉아도 된다.
따라서, 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
의 2번 조건을 따라서 나와 인접한 친구들 자리가 제일 많이 비어있는 (;4) 파이썬 인덱싱 기준으로 (1,1) 자리에 앉게 된다. = 놀 친구들이 제일 많은 center !
=> 즉 맨 처음 번호인 학생은 무조건 파이썬 인덱싱을 기준으로 했을 때 주변 4 좌석이 모두 비어있는 (1,1) 자리에 앉아야 한다.
def solve(self):
self.put=[]
self.Cand=[]
x=0 #변수 선언
y=0 #변수 선언
for i in range(self.n**2):
cand=[]
if i==0:
x=1
y=1
self.cell[1][1]=self.info[i][0]
그리고 가운데에 4번 학생이 앉았으므로 4번 주변의 empty 값엔 변경 사항이 있으므로 이제 새로 갱신해줘야한다.
self.empty[x-1][y]-=1
self.empty[x][y-1]-=1
self.empty[x][y+1]-=1
self.empty[x+1][y]-=1
그리고 4번 학생이 앉은 좌석 좌표와, 4번 학생이 앉은 좌석의 인접한 칸 좌표를 각각 put, Cand 에 저장해준다.
self.put.append(self.info[i][0])
cand.append((x-1,y))
cand.append((x,y-1))
cand.append((x,y+1))
cand.append((x+1,y))
self.Cand.append(cand)
여기까지 코드를 합쳐서 보면,
def solve(self):
self.put=[]
self.Cand=[]
x=0 #변수 선언
y=0 #변수 선언
for i in range(self.n**2):
cand=[]
if i==0:
x=1
y=1
self.cell[1][1]=self.info[i][0]
self.empty[x-1][y]-=1
self.empty[x][y-1]-=1
self.empty[x][y+1]-=1
self.empty[x+1][y]-=1
self.put.append(self.info[i][0])
cand.append((x-1,y))
cand.append((x,y-1))
cand.append((x,y+1))
cand.append((x+1,y))
self.Cand.append(cand)
이다.
이제 두 번째 순서의 학생부터는, 자신보다 이전 번호 학생들은 자리에 이미 앉아있다.
- 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
의 1번 조건에 제일 적합한 자리가 무엇인지 구해주기 위해서
put 에 저장되어있는 이전 학생들을 현재 순서의 학생이 좋아하는지를 먼저 체크해주고, 만약 좋아한다면 put 에 저장되어있는 이전 학생의 인접한 칸이 현재 순서의 학생이 앉아야 할 유력한 후보 좌석이 된다. 즉 자기가 좋아하는 학생이 이미 앉아있고, 비어있는 자리 중 자기가 좋아하는 그 학생과 인접한 자리는 모두 후보 좌석 (;sit_cand) 에 들어가는 것이다.
else: #i>0
sit_cand=[]
for j in range(len(self.put)):
if self.put[j] in self.info[i][1:] : #put 에 저장되어있는 이전 학생 좋아함 !
for coor in self.Cand[j]:
if self.cell[coor[0]][coor[1]]==0:
sit_cand.append(coor)
따라서 가령 (0,1) 번 좌석이 내가 좋아하는 4번이 앉은 자리와도 인접하고, 내가 좋아하는 3번이 앉은 자리와도 인접하다면 (0,1) 은 sit_cand 에 두 번 들어갈 것이다. 각 좌석별로 sit_cand 에 몇 번 씩 들어가있는지 세어준다.(;딕셔너리 Count 에 저장) 1번 조건에 의해서 count 가 가장 큰 좌석에 앉아야 한다.
if len(sit_cand)>0:
Count=dict()
for coor in sit_cand:
Count[coor]=sit_cand.count(coor)
그리고 3번 조건까지 넘어갈 가능성이 있는데 3번 조건은 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다. 이므로 귀찮으니까 미리 정렬을 해준다.
it=list(Count.items())
it=sorted(it,key=lambda x:x[0])
val=[K[1] for K in it]
val 에는 차례대로 정렬된 좌표마다 sit_cand 에 몇 번씩 들어갔는지 value 가 저장되어있다.
만약, 1을 만족하는 칸이 여러 개이면 2번 조건으로 넘어가야 한다
if val.count(max(val))>1: # 1번 조건 -> 2번 조건
2번 조건은, 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 이다
이제 empty 를 활용할 때가 되었다. 각 좌표별로 인접한 칸이 몇 개나 비어있는지가 저장되어있는 empty 를 확인해본다.
단, 1을 만족하는 칸이어야 한다. one_passed 에는 어떠한 칸의 빈 인접한 칸 개수를 세어주는 건지, 그 칸에 대한 정보를 담아주고, how_empty 에는 one_passed 에 저장된 칸 (;1을 만족한느 칸) 의 빈 인접한 개수를 담아준다.
for k in range(len(it)):
if it[k][1]==max(val): #1번 조건을 만족한다면
one_passed.append(it[k][0])
how_empty.append(self.empty[it[k][0][0]][it[k][0][1]])
만약, 2번 조건을 만족하는 칸도 여러 개라면 3번 조건으로 넘어가야 한다.
if how_empty.count(max(how_empty))>1: #2번 조건 -> 3번 조건
3번 조건은, 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다. 이다.
미리 it 은 행 과 열 이 작은 순으로 다 정렬했기 때문에 제일 앞에 꺼를 빼주고 break 해주면 된다. 단, 2를 만족하는 칸인 경우 !
if how_empty.count(max(how_empty))>1: #2번 조건 -> 3번 조건
for w in range(len(how_empty)):
if how_empty[w]==max(how_empty): #2번 조건을 만족한다면
x=one_passed[w][0]
y=one_passed[w][1]
break
반면 2번 조건을 만족하는 칸이 딱 하나여서 3번 조건으로 넘어갈 필요가 없다면, 바로 현재 순서의 학생이 앉아야 할 x,y 좌표를 구할 수 있다.
else: # if how_empty.count(max(how_empty))==1: # 2번 조건 -> 3번 조건으로 안 넘어가도 된다 !
r=how_empty.index(max(how_empty))
x=one_passed[r][0]
y=one_passed[r][1]
마찬가지로 아까 1번 조건을 만족하는 좌석이 여전히 너무 많아서 2번 조건으로 계속 넘어갔다면, 1번 조건을 만족하는 칸이 딱 하나여서 2번 조건으로 애초에 넘어갈 필요가 없는 경우에는 1번 조건의 max(val) 인덱스가 바로 현재 순서의 학생이 앉아야 할 x,y 좌표이다.
else: # if val.count(max(val))==1: # 1번 조건 -> 2번 조건으로 안 넘어가도 된다 !
r=val.index(max(val))
x=it[r][0][0]
y=it[r][0][1]
반면, 이미 자리에 앉은 학생들 중에는 현재 순서의 학생이 좋아하는 사람이 한 명도 없다면 sit_cand 는 0이 될 것이다. 이 경우에 아까 맨 처음 순서와 마찬가지로 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 에 해당하는 자리가 딱히 없다. = 2번 조건이 없다면 아무 데나 앉아도 된다. 따라서, 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 **비어있는 칸이 가장 많은 칸으로 자리를 정한다.**
2번 조건까지 만족할 경우, 행,열이 제일 작은 좌석을 배정하는 3번 조건으로 넘어가야 한다. 미리 이것까지 고려해두는 게 좋을 듯 했다.
else: #len(sit_cand)==0 ! 이미 자리에 앉은 학생 중 좋아하는 학생 없음 !
Maxx=0
for l in range(self.n-1,-1,-1):
for m in range(self.n-1,-1,-1):
if self.cell[l][m]==0:
if self.empty[l][m]>=Maxx:
Maxx=self.empty[l][m]
x=l
y=m
가령
총 100명의 학생이 있다고 하고, 첫 번째 순서 학생 10번이 17번 / 77번 / 1번 / 30번 을 좋아한다고 하고,
두 번째 순서 학생 38번은 53번 / 84번 / 9번 / 68번을 좋아한다고 하면, 앉은 학생은 10번 뿐이지만 38번 학생은 10번을 좋아하지 않으므로 sit_cand 는 0이다.
이 때 self.empty[l][m]>=Maxx 에서 조건이 등호가 아니라 부등호이므로, 현재까지 비어있는 칸 중 최대 값을 가진 좌표와 그 보다 행과 열이 더 작은 좌표의 비어있는 칸 개수가 같거나 더 크다면 3번 조건에서 행과 열이 더 작은 좌표를 선택하게 된다.
이로써 모든 경우를 고려해서, 현재 순서의 학생이 앉아야 할 자리를 구했다.
여기까지 전체 코드는 다음과 같다.
import sys
input=sys.stdin.readline
class Sclass:
def read(self):
self.n=int(input())
self.info=[list(map(int,input().split())) for _ in range(self.n**2)]
self.cell=[[0]*self.n for i in range(self.n)]
self.empty=[[3]*self.n for i in range(self.n)]
self.empty[0][0]=2
self.empty[0][self.n-1]=2
self.empty[self.n-1][0]=2
self.empty[self.n-1][self.n-1]=2
for p in range(self.n):
for q in range(self.n):
if p>0 and q>0:
if p<self.n-1 and q<self.n-1:
self.empty[p][q]=4
def solve(self):
self.put=[]
self.Cand=[]
x=0 #변수 선언
y=0 #변수 선언
for i in range(self.n**2):
cand=[]
if i==0:
x=1
y=1
self.cell[1][1]=self.info[i][0]
self.empty[x-1][y]-=1
self.empty[x][y-1]-=1
self.empty[x][y+1]-=1
self.empty[x+1][y]-=1
self.put.append(self.info[i][0])
cand.append((x-1,y))
cand.append((x,y-1))
cand.append((x,y+1))
cand.append((x+1,y))
self.Cand.append(cand)
else:
sit_cand=[]
for j in range(len(self.put)):
if self.put[j] in self.info[i][1:] :
for coor in self.Cand[j]:
if self.cell[coor[0]][coor[1]]==0:
sit_cand.append(coor)
if len(sit_cand)>0:
Count=dict()
for coor in sit_cand:
Count[coor]=sit_cand.count(coor)
it=list(Count.items())
it=sorted(it,key=lambda x:x[0])
val=[K[1] for K in it]
if val.count(max(val))>1: # 1번 조건 -> 2번 조건
one_passed=[]
how_empty=[]
for k in range(len(it)):
if it[k][1]==max(val):
one_passed.append(it[k][0])
how_empty.append(self.empty[it[k][0][0]][it[k][0][1]])
if how_empty.count(max(how_empty))>1: #2번 조건 -> 3번 조건
for w in range(len(how_empty)):
if how_empty[w]==max(how_empty):
x=one_passed[w][0]
y=one_passed[w][1]
break
else:
r=how_empty.index(max(how_empty))
x=one_passed[r][0]
y=one_passed[r][1]
else:
r=val.index(max(val))
x=it[r][0][0]
y=it[r][0][1]
else:
Maxx=0
for l in range(self.n-1,-1,-1):
for m in range(self.n-1,-1,-1):
if self.cell[l][m]==0:
if self.empty[l][m]>=Maxx:
Maxx=self.empty[l][m]
x=l
y=m
그러면 현재 순서가 앉아야 할 자리를 구했으므로, 해당 자리에 현재 순서 학생을 앉힌다.
self.cell[x][y]=self.info[i][0]
그 다음으로 마찬가지로, empty 를 갱신해주고, 현재 학생이 앉은 좌석 좌표와, 현재 학생이 앉은 좌석의 인접한 칸 좌표를 각각 put, Cand 에 저장해준다.
if x-1>=0 and y>=0:
if x-1<=self.n-1 and y<=self.n-1:
self.empty[x-1][y]-=1
cand.append((x-1,y))
if x>=0 and y-1>=0:
if x<=self.n-1 and y-1<=self.n-1:
self.empty[x][y-1]-=1
cand.append((x,y-1))
if x>=0 and y+1>=0:
if x<=self.n-1 and y+1<=self.n-1:
self.empty[x][y+1]-=1
cand.append((x,y+1))
if x+1>=0 and y>=0:
if x+1<=self.n-1 and y<=self.n-1:
self.empty[x+1][y]-=1
cand.append((x+1,y))
self.put.append(self.info[i][0])
self.Cand.append(cand)
다음으로 이제 학생의 만족도를 구해야 한다. 학생의 만족도는 자리 배치가 모두 끝난 후에 구할 수 있다. 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.
학생 만족도를 구하는 ans 함수는 훨씬 간단하게 작성할 수 있었다.
def ans(self):
ans=0
for j in range(len(self.Cand)):
s=0
for nb in self.Cand[j]:
if self.cell[nb[0]][nb[1]] in self.info[j][1:]:
s+=1
if s==2:
ans+=10
elif s==3:
ans+=100
elif s==4:
ans+=1000
elif s==0 or s==1:
ans+=s
print(ans)
전체 코드
import sys
input=sys.stdin.readline
class Sclass:
def read(self):
self.n=int(input())
self.info=[list(map(int,input().split())) for _ in range(self.n**2)]
self.cell=[[0]*self.n for i in range(self.n)]
self.empty=[[3]*self.n for i in range(self.n)]
self.empty[0][0]=2
self.empty[0][self.n-1]=2
self.empty[self.n-1][0]=2
self.empty[self.n-1][self.n-1]=2
for p in range(self.n):
for q in range(self.n):
if p>0 and q>0:
if p<self.n-1 and q<self.n-1:
self.empty[p][q]=4
def solve(self):
self.put=[]
self.Cand=[]
x=0 #변수 선언
y=0 #변수 선언
for i in range(self.n**2):
cand=[]
if i==0:
x=1
y=1
self.cell[1][1]=self.info[i][0]
self.empty[x-1][y]-=1
self.empty[x][y-1]-=1
self.empty[x][y+1]-=1
self.empty[x+1][y]-=1
self.put.append(self.info[i][0])
cand.append((x-1,y))
cand.append((x,y-1))
cand.append((x,y+1))
cand.append((x+1,y))
self.Cand.append(cand)
else:
sit_cand=[]
for j in range(len(self.put)):
if self.put[j] in self.info[i][1:] :
for coor in self.Cand[j]:
if self.cell[coor[0]][coor[1]]==0:
sit_cand.append(coor)
if len(sit_cand)>0:
Count=dict()
for coor in sit_cand:
Count[coor]=sit_cand.count(coor)
it=list(Count.items())
it=sorted(it,key=lambda x:x[0])
val=[K[1] for K in it]
if val.count(max(val))>1: # 1번 조건 -> 2번 조건
one_passed=[]
how_empty=[]
for k in range(len(it)):
if it[k][1]==max(val):
one_passed.append(it[k][0])
how_empty.append(self.empty[it[k][0][0]][it[k][0][1]])
if how_empty.count(max(how_empty))>1: #2번 조건 -> 3번 조건
for w in range(len(how_empty)):
if how_empty[w]==max(how_empty):
x=one_passed[w][0]
y=one_passed[w][1]
break
else:
r=how_empty.index(max(how_empty))
x=one_passed[r][0]
y=one_passed[r][1]
else:
r=val.index(max(val))
x=it[r][0][0]
y=it[r][0][1]
else:
Maxx=0
for l in range(self.n-1,-1,-1):
for m in range(self.n-1,-1,-1):
if self.cell[l][m]==0:
if self.empty[l][m]>=Maxx:
Maxx=self.empty[l][m]
x=l
y=m
self.cell[x][y]=self.info[i][0]
if x-1>=0 and y>=0:
if x-1<=self.n-1 and y<=self.n-1:
self.empty[x-1][y]-=1
cand.append((x-1,y))
if x>=0 and y-1>=0:
if x<=self.n-1 and y-1<=self.n-1:
self.empty[x][y-1]-=1
cand.append((x,y-1))
if x>=0 and y+1>=0:
if x<=self.n-1 and y+1<=self.n-1:
self.empty[x][y+1]-=1
cand.append((x,y+1))
if x+1>=0 and y>=0:
if x+1<=self.n-1 and y<=self.n-1:
self.empty[x+1][y]-=1
cand.append((x+1,y))
self.put.append(self.info[i][0])
self.Cand.append(cand)
def ans(self):
ans=0
for j in range(len(self.Cand)):
s=0
for nb in self.Cand[j]:
if self.cell[nb[0]][nb[1]] in self.info[j][1:]:
s+=1
if s==2:
ans+=10
elif s==3:
ans+=100
elif s==4:
ans+=1000
elif s==0 or s==1:
ans+=s
print(ans)
sclass=Sclass()
sclass.read()
sclass.solve()
sclass.ans()
테스트 케이스 (현재 100명으로 설정되어있음)
import random
ch=[]
print(10)
for i in range(100):
a=[]
s=0
while len(a)<5:
x=random.randint(1,100)
if s==0 :
if x not in ch:
a.append(x)
s+=1
elif x not in a:
a.append(x)
ch.append(a[0])
for i in range(5):
if i<4:
print(a[i],end=' ')
elif i==4:
print(a[i],end='\n')
문제 자체는 정말 메뉴얼대로만 했으면 되는데, 정말 사소한 부분에서 코드를 잘못 작성해서 생각보다 많이 방황했다 !