[백준] 21608 상어 초등학교

백준 21608번 상어 초등학교

구현


실버1 치고 생각보다 어려웠던 문제
문제를 풀다보니 이전엔 dfs와 같은 그래프가 어렵다 생각했는데 이제는 구현이 가장 까다롭고 복잡한 것 같다.

[문제]

노란 부분이 구현의 핵심이 되는 알고리즘 이다.
1,2번은 같이 구할 수 있고 마지막에 학생이 인접한 수, 비어있는 칸수, x행, y열로 정렬을 해주면 된다.

위에까지 좌표를 완성한 후 만족도까지 구해야 한다.
좌표만큼 반복문을 돌리고 해당 값만큼 조건문으로 값을 더해주자.

[과정]

※ 좌표 저장하기

1. 학생수(students)만큼 반복
1-1) 좌표만큼(n*n)만큼 반복
1-2) 해당 좌표가 아무값도 없을시(-1) 인접한 경로(상하좌우)를 탐색
1-3) 배열(arr)에 인접한 학생수, 인접한 빈칸 수, x좌표, y좌표를 저장 (cnt, empty, x, y)
1-4) lambda 함수를 사용하여 학생수, 빈칸수는 내림차순, x좌표, y좌표는 오름차순으로 순서대로 정렬


※ 만족도 구하기

2. n*n만큼 반복
2-1) 해당 좌표의 값(num)을 구하여 변수(data)에 해당 학생을 좋아하는 번호를 저장
2-2) 상하좌우를 비교하여 인접한 좌표값의 값이 data에 있으면 cnt에 1추가
2-3) 인접한 학생수(cnt)에 따른 별개의 만족도 값을 변수(ans)에 저장하여 최종 출력



※ 테스트 케이스는 맞는데 '틀렸습니다.' 뜨는 경우 ※
나의 경우였다.

나의 코드중 '# 수정' 부분을 보면 기존에는 for문이 없었는데 for문을 추가해줬다.
그 이유는 해당 번호 주변에 좋아하는 학생들이 없는데 앉을 자리가 많은 경우 첫번째 자리에 값이 계속 덮어 씌워지는 오류가 있었다.




해당 테스트 케이스를 돌려보고 확인해보자.

case1)

4
1 1 2 3 4
2 1 2 3 4
3 1 2 3 4
4 1 2 3 4
5 1 2 3 4
6 1 2 3 4
7 1 2 3 4
8 1 2 3 4
9 1 2 3 4
10 1 2 3 4
11 1 2 3 4
12 1 2 3 4
13 1 2 3 4
14 1 2 3 4
15 1 2 3 4
16 1 2 3 4

답: 48

완성된 배열

13 5 9 14
6 1 2 7
10 3 4 11
15 8 12 16



출처: https://jamluck.tistory.com/5 [잼럭의 기록저장소]

case2)

3
1 2 3 4 5
2 1 3 4 5
3 1 2 4 5
4 1 2 3 5
5 1 2 3 4
6 1 2 3 4
7 1 2 3 4
8 1 2 3 4
9 1 2 3 4

답 : 134



출처: https://jamluck.tistory.com/5 [잼럭의 기록저장소]

[소스코드]

 

# 상어 초등학교

n = int(input())
students = [0] * (n*n)

for i in range(n*n):
    students[i] = list(map(int, input().split()))
    
graph = [[-1]*n for i in range(n)]
nx = [1,-1,0,0]
ny = [0,0,1,-1]

# 좌표 저장
for student in students:
    arr = []
    for i in range(n):
        for j in range(n):
            cnt = 0
            empty = 0            
            if graph[i][j] == -1:
                for k in range(4):
                    x = i + nx[k]
                    y = j + ny[k]
                    if x < 0 or x >= n or y < 0 or y >= n:
                        continue
                    if graph[x][y] == -1:
                        empty += 1
                    elif graph[x][y] in student[1:]:
                        cnt += 1
            arr.append((cnt,empty,i,j))

    # 수정
    result = sorted(arr, key = lambda x : (-x[0], -x[1], x[2], x[3]))
    for r in result:
        if graph[r[2]][r[3]] == -1:
            graph[r[2]][r[3]] = student[0]
            break

# 만족도 구하기
ans = 0
for i in range(n):
    for j in range(n):
        for s in students:
            if s[0] == graph[i][j]:
                num = s
                data = s[1:]          
        sat = 0       
        for k in range(4):
            x = i + nx[k]
            y = j + ny[k]
            if x < 0 or x >= n or y < 0 or y >= n:
                continue
            if graph[x][y] in data:
                sat += 1
        if sat != 0:
            ans += 10 ** (sat-1)
print(ans)

---

[정답]

 

 

 

 

 

---

 

 

[두번째로 풀었던 코드]

 

# 2022.03.18 상어초등학교
# 알고리즘 스터디 1주차

n = int(input())
arr = [[0]*n for _ in range(n)]

student = []
for _ in range(n*n):
    m = list(map(int, input().split()))
    student.append(m)

dx = [1,-1,0,0]
dy = [0,0,-1,1]
    
# 좋아하는 학생이 인접한 수, 인접한칸중 비어있는칸수, 행, 열 순
for s in student:
    s1 = s[0]
    s2 = s[1:]
    maps= [] # 계산완료된 것
    
    for i in range(n):
        for j in range(n):
            # 첫번째 두번째
            cnt_1 = 0
            cnt_2 = 0
            
            if arr[i][j] != 0:
                continue
            
            for k in range(4):
                x = i + dx[k]
                y = j + dy[k]
                if x < 0 or x >= n or y < 0 or y >= n:
                    continue
                if arr[x][y] in s2:
                    cnt_1 += 1
                elif arr[x][y] == 0:
                    cnt_2 += 1
            maps.append([cnt_1, cnt_2, i, j])
    # 한사이클
    # 람다로 정렬
##    print('이전의 maps', maps)
    maps.sort(key = lambda x:(-x[0],-x[1],x[2],x[3]))
##    print('maps',maps)
    data = maps[0]
##    print('data',data)
    arr[data[2]][data[3]] = s1
##    print('arr',arr)
##    print()
    
                
# 만족도구하기
result = 0
for i in range(n):
    for j in range(n):
        cnt = 0
        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]
            if x < 0 or x >= n or y < 0 or y >= n:
                continue
            for s3 in student:
                if arr[i][j] == s3[0]:
                    if arr[x][y] in s3[1:]:
                        cnt+=1
                        
        if cnt == 0:
            result += 0
        elif cnt == 1:
            result += 1
        elif cnt == 2:
            result += 10
        elif cnt == 3:
            result += 100
        elif cnt == 4:
            result += 1000
print(result)

스터디를 하면서 다시한번 풀어보게 되었다.

이미 한번 풀었던 거였는데 1시간 반이나 걸렸다...ㅜㅜ

 

 

[원큐로 정답]

그래도 한번 풀었었다고 풀이과정이 좀 기억이 났다.

처음 풀었을때는 몇번틀리고 맞았는데 이번엔 한번에 푼것에 의의를 둔다!ㅎㅎ