[코드트리/삼성SW역량테스트/백준/21608] 놀이기구 탑승 / 상어 초등학교 (Python)

Problem1 : https://www.codetree.ai/training-field/frequent-problems/problems/go-on-the-rides

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

Problem2 : https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:11:40

 

---

 

문제 설명 / 입력 및 출력

 

 

자세한 설명은 코드트리 사이트 링크를 참조해 주세요!

 

 

---

 

풀이

 

두 번째 복습 문제 되시겠다. 그대로 구현하면 되는 문제. 우선순위 탐색 및 조건에 해당하는 좌표 탐색만 철저하게 한다면 틀릴 일 자체는 많이 없고, 이 문제를 헤맨다면 비슷한 구현 문제를 더 풀어보는 게 맞다고 개인적으로 생각이 든다.

 

 

풀이 코드(1년전)

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


N = int(input())
lst = dict()
for _ in range(N**2):
  key, *val = map(int, input().split())
  lst[key] = val
cls = [[0]*N for _ in range(N)]
empty =[(i, j) for i in range(N) for j in range(N)]

for num in lst :
  tmp_lst = []
  for i, (x, y) in enumerate(empty):
    p, e = 0, 0
    for j in range(4):
      ax, ay = x+dx[j], y+dy[j]
      if -1<ax<N and -1<ay<N :
        if cls[ay][ax] in lst[num] :
          p += 1
        elif cls[ay][ax] == 0:
          e += 1
    tmp_lst.append((p, e, y, x, i))
  tmp_lst.sort(key = lambda x : (-x[0], -x[1], x[2], x[3]))
  _, _, y, x, i = tmp_lst[0]
  del empty[i]
  cls[y][x] = num

ans = 0
for i in range(N):
  for j in range(N):
    cnt = 0
    num = cls[i][j]
    for k in range(4):
      if -1 < i+dy[k] < N and -1 < j+dx[k] < N and cls[i+dy[k]][j+dx[k]] in lst[num] :
        cnt += 1
    ans += 0 if cnt == 0 else 10**(cnt-1)
print(ans)

 

 

풀이 코드

import sys
input = sys.stdin.readline

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

N = int(input())

friend_dict = dict()
maps = [[0]*N for _ in range(N)]

def find_best_seat(n) :
    bf, be, br, bc = 5, 5, N, N 
    for i in range(N) :
        for j in range(N) :
            if maps[i][j] == 0 :
                f, e = 4, 4
                for k in range(4) :
                    r, c = i + dr[k], j + dc[k]
                    if -1 < r < N and -1 < c < N :
                        if maps[r][c] in friend_dict[n]:
                            f -= 1
                        elif not maps[r][c] :
                            e -= 1
                if (bf, be, br, bc) > (f, e, i, j) :
                    bf, be, br, bc = f, e, i, j
    maps[br][bc] = n

def cal_score() :
    result = 0
    for i in range(N) :
        for j in range(N) :
            n = maps[i][j]
            cnt = 0
            for k in range(4) :
                r, c = i + dr[k], j + dc[k]
                if -1 < r < N and -1 < c < N and maps[r][c] in friend_dict[n] :
                    cnt += 1
            if cnt :
                result += 10 ** (cnt-1)
    print(result)

for _ in range(N**2) :
    n, *friend = map(int, input().split())
    friend_dict[n] = friend
    find_best_seat(n)
cal_score()

풀이 완료!