<BOJ>21608번: 상어 초등학교
문제
접근
- 다음 케이스를 잘 분류해야 한다. 이 케이스를 계산하고 정렬 과정 역시 필요하다.
- 비어있는 칸 중 좋아하는 학생이 인접 자리에 많은 곳에 위치 지정
- 1번 조건 해당 케이스가 여러 개면 인접 칸 중 빈자리 개수가 가장 많은 곳에 위치 지정
- 2번 조건 해당 케이스가 여러 개면 행 번호가 최소인 자리 → 열 번호 최소인 자리
- 형태가 복잡한 중첩 리스트와, 딕셔너리를 잘 활용해야 한다.
- 탐색은 BFS를 푸는 것과 유사하게 접근하면 된다.
- 탐색하는 인덱스 위치가 자리선정이 된 곳인지 True, False로 따로 판별하려 했지만, 그것보단 3*3 배열 자체가 0으로 셋팅됐다가 0이 아닌 값으로 채워지면 자리선정이 된 것이므로 이를 활용하는게 더 간단했다.
내 코드
# BOJ 21608번: 상어 초등학교
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
n = int(input())
n_square = n ** 2
students = [list(map(int, input().split())) for _ in range(n_square)]
arr = [[0] * n for _ in range(n)]
for s in range(n_square):
tmp = []
for i in range(n):
for j in range(n):
sumLike, sumEmpty = 0, 0
if arr[i][j] != 0:
continue
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
if nx < 0 or nx > n-1 or ny < 0 or ny > n-1:
continue
if arr[nx][ny] in students[s][1:]:
sumLike += 1
if arr[nx][ny] == 0:
sumEmpty += 1
tmp.append((sumLike, sumEmpty, (i, j)))
tmp.sort(key=lambda x: (-x[0], -x[1], x[2]))
arr[tmp[0][2][0]][tmp[0][2][1]] = students[s][0]
# print(arr)
# print(students)
likes = {}
for i in range(n_square):
tmp = students[i][0]
likes[tmp] = students[i][1:]
# print(likes)
result = 0
for i in range(n):
for j in range(n):
cnt = 0
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
if nx < 0 or nx > n - 1 or ny < 0 or ny > n - 1:
continue
if arr[nx][ny] in likes[arr[i][j]]:
cnt += 1
continue
if cnt != 0:
result += 10 ** (cnt - 1)
print(result)
# BOJ 21608번: 상어 초등학교
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
n = int(input())
n_square = n ** 2
students = [list(map(int, input().split())) for _ in range(n_square)]
arr = [[0] * n for _ in range(n)]
for s in range(n_square):
tmp = []
for i in range(n):
for j in range(n):
sumLike, sumEmpty = 0, 0
if arr[i][j] != 0:
continue
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
if nx < 0 or nx > n-1 or ny < 0 or ny > n-1:
continue
if arr[nx][ny] in students[s][1:]:
sumLike += 1
if arr[nx][ny] == 0:
sumEmpty += 1
tmp.append((sumLike, sumEmpty, (i, j)))
tmp.sort(key=lambda x: (-x[0], -x[1], x[2]))
arr[tmp[0][2][0]][tmp[0][2][1]] = students[s][0]
# print(arr)
# print(students)
likes = {}
for i in range(n_square):
tmp = students[i][0]
likes[tmp] = students[i][1:]
# print(likes)
result = 0
for i in range(n):
for j in range(n):
cnt = 0
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
if nx < 0 or nx > n - 1 or ny < 0 or ny > n - 1:
continue
if arr[nx][ny] in likes[arr[i][j]]:
cnt += 1
continue
if cnt != 0:
result += 10 ** (cnt - 1)
print(result)
if arr[nx][ny] in students[s][1:]:
과 같이 in
으로 포함 여부를 편리하게 추출할 수 있으므로 이를 잘 활용하는 연습을 해봐야 할 것 같다. 덧붙여 likes[tmp] = students[i][1:]
와 같이 리스트 슬라이싱을 하는 것도 굉장히 편리했다. 또한 key를 기준으로 정렬하는 부분이 굉장히 편리하다.
// 최근 SK 1차 코딩테스트 당일 부터 파이썬을 사용하기 시작했는데, 문법만 익숙해지면 자바를 사용하는 것 보다 훨씬 편하게 풀이할 것 같다.
Author And Source
이 문제에 관하여(<BOJ>21608번: 상어 초등학교), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@songs4805/BOJ21608번-상어-초등학교저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)