개구리

우물 안 개구리

구현 문제는 코드를 작성하면서도 너무 복잡한 것 아닌가 하는 의문이 든다. 그러나 의문을 뒤로 하고 일단 끝까지 풀 수 있다.

N= int(input())
room=[[0 for _ in range(N)] for _ in range(N)] #채워진 상태

wanted=[[] for _ in range(1+ N**2)] # 내가 원하는 친구들
assigned=[[-1,-1] for _ in range (1+ N**2)] #배정받았는지 체크하기
#위, 왼, 오, 아래 순서
dx=[0,-1,1,0]
dy=[1,0,0,-1]

def check_blank(x,y): # x , y 주위의 4칸에 빈칸이 몇개나 있는가?
    count=0
    for i in range(4):
        nx= x+dx[i]
        ny= y+dy[i]
        if 0<=nx< N and 0<=ny<N and room[ nx ][ ny ] ==0:
            count+=1
    
    return count

sol=0
score=[0,1,10,100,1000]

for i in range(N**2):
    student, f1,f2,f3,f4 = map(int, input().split())
    wanted[student]=[f1,f2,f3,f4]
    
    #각 학생 배치를 위해 배열 넣어두기
    tmp=[ [], [], [], [] ]
    for j in range(4): #원하는 친구 4명 모두 돌려보자
        freind = wanted[student][j]
        location_friend=assigned[freind]
        
        if location_friend==[-1,-1]: #친구가 아직 배치되어 있지 않다면 
            # print("배치해야될사람/ 그 친구",student, freind)
            continue
        
        for k in range(4): 
            nx=location_friend[0]+dx[k] 
            ny=location_friend[1]+dy[k] #친구 배치된 곳 주위 4방향 우선순위대로 보자
            if 0<=nx<N and 0<=ny<N and room[nx][ny]==0: #아직 배치되어있지 않고 격자를 벗어나지 않으면 배치는 가능
                    blank=check_blank(nx,ny)
                    plan = [nx,ny, blank]
                    if plan not in tmp[0]:
                        tmp[0].append(plan)
                    else:
                        if plan not in tmp[1]:
                            tmp[1].append(plan)
                        else:
                            if plan not in tmp[2]:
                                tmp[2].append(plan)
                            else:
                                tmp[3].append(plan)

    select=[-1,-1]
    for l in range(3,-1,-1):
        if tmp[l]!=[] :
            tmp[l].sort(key=lambda x: (-x[2], x[0], x[1]))
            select=tmp[l][0]
            break
    
    if select==[-1,-1]:
        ans=0
        ans1=[]
        for x in range(N):
            for y in range(N):
                if room[x][y]==0:
                    blank=check_blank(x,y)
                    
                    if ans < blank :
                        ans=blank
                        select=[x,y]
                    
                    if blank==0:
                        ans1.append([x,y])
                        
                    
        if ans==0:
            select=ans1[0]
                
       
    assigned[student]= select
    room[ select[0] ][ select[1] ]= student

for i in range(1, 1+N**2):
    how=0
    x,y = assigned[i][0], assigned[i][1] # 학생의 위치
    
    for j in range(4):
        nx ,ny = x+dx[j], y+dy[j]
        if 0<=nx<N and 0<=ny<N :
            who = room[nx][ny] # 내 주위에는 누가 있을까

            if who in wanted[i] :
                how +=1
                
    sol+=score[how]
        

print(sol)

문제 설계

wanted - 인덱스에 해당하는 학생이 좋아하는 학생 4명의 번호를 저장한다.

room - 격자판에 아무도 배정되지 않으면 0을 배정되어 있다면 학생의 번호를 저장한다.

assigned - 해당 인덱스의 학생이 배정된 위치를 저장한다. room 배열에서 확인해도 되지만 빠른 연산을 위해 메모리를 더 사용하는 방향을 선택했다.

def check_blank(x,y) : 좌표가 주어지면 4방향을 모두 탐색하여 빈 칸이 얼마나 있는지 계산하여 반환한다.

구현

학생 1명(student) 당 wanted 배열에 4명의 학생 (f1,f2,f3,f4) 이 있다. 4명의 학생을 각각 루프 내에서 처리한다.

  1. assigned 배열을 이용하여 배정 여부를 체크한다.
  2. 4명의 학생 중 한 명이 위치 (location_friend)에 배정되었다면 인접한 b1,b2,b3,b4(nx,ny로 좌표 표현)이 각각 빈 칸인지 확인한다.
  3. b1,b2,b3,b4 중에서 빈 칸을 blank_check 함수의 인자로 전달하여 인접한 곳의 blank를 계산한다.
  4. b1,b2,b3,b4 중 빈칸의 위치와 함께 blank 정보를 tmp 배열에 저장한다.
  5. tmp에는 student가 배정될 수 있는 위치가 저장되게 된다. 이 때 tmp에 중복되는 위치를 표시하기 위해 tmp를 2차원 리스트로 만든다. tmp[3]에 저장되는 위치는 인접한 4방향에 모두 좋아하는 학생이 배정되어 있다.
  6. 인접한 방향에 더 많은 학생들이 위치한 경우가 최우선이므로 tmp의 인덱스를 뒤에서 부터 본다. 그 다음으로 비어있는 칸이 가장 많은 경우, 행과 열의 번호가 작은 경우의 순서를 알아야하므로 정렬한다. 정렬 결과 가장 먼저 등장하는 위치를 select에 저장한다.
  7. 만약 tmp에 아무것도 없을 경우, 즉 4명의 학생이 모두 배정이 되지 경우에는 루프를 돌려가며 빈 칸의 개수가 더 큰 위치가 등장하면 ans를 갱신하여 select에 저장한다.
  8. 모든 학생을 배치하고 점수를 계산한다.

더 알아보기

좋아하는 학생과 인접한 곳에 배치할 수 없고 인접한 빈 칸이 모두 0인 위치에 학생을 배정해야 되는 경우가 발생한다. 이를 위해 ans1를 만들었는데 코드를 정리하면 좀 더 간단하게 표현할 수 있을 것 같다. 구현 문제는 코드를 간결하게 다시 푸는 과정이 필요할 것 같다.

댓글남기기

참고