[Algorithm] 백준 알고리즘 - 삼성 2020 기출
문제(16236번)
내가 푼 답(못풀음)
import heapq
n = int(input())
graph = []
global result
result = 0
for _ in range(n):
graph.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def dfs(a, b, size, count, time):
if a < 0 or a >= n or b < 0 or b >= n:
return False
if size < graph[a][b]:
return False
elif size > graph[a][b] and graph[a][b] != 0:
count += 1
result += time
time = 0
if size == count:
size += 1
count = 0
graph[a][b] == 0
#0인 경우
elif graph[a][b] == 0 or graph[a][b] == size:
time += 1
for i in range(4):
dfs(dx[i]+a, dy[i]+b, size, count, time)
start = []
for a in range(n):
for b in range(n):
if graph[a][b] == 9:
start.append((a, b))
graph[a][b] = 0
a, b = start.pop()
dfs(a, b, 2, 0, 0)
print(result)
답안 예시
from collections import deque
INF = int(1e9)
n = int(input())
array = []
for i in range(n):
array.append(list(map(int, input().split())))
now_size = 0
now_x, now_y = 0, 0
for i in range(n):
for j in range(n):
if array[i][j] == 9:
now_x, now_y = i, j
array[now_x][now_y] = 0
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def bfs():
dist = [[-1] * n for _ in range(n)]
q = deque([now_x, now_y])
dist[now_x][now_y] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx and nx < n and 0 <= ny and ny < n:
if dist[nx][ny] == -1 and array[nx][ny] <= now_size:
dist[nx][ny] = dist[x][y] +1
q.append((nx, ny))
return dist
#최단거리 테이블에서 먹을 물고기 찾기
def find(dist):
x, y = 0, 9
min_dist = INF
for i in range(n):
for j in range(n):
if dist[i][j] != -1 and 1 <= array[i][j] and array[i][j] < now_size:
if dist[i][j] < min_dist:
x, y = i, j
min_dist = dist[i][j]
if min_dist == INF:
return None
else:
return x, y, min_dist
result = 0
ate = 0
while True:
value = find(bfs())
if value == None:
print(result)
break
else:
now_x, now_y = value[0], value[1]
result += value[2]
array[now_x][now_y] = 0
ate += 1
if ate >= now_size:
now_size += 1
ate = 0
고찰
내가 풀었던 풀이는 dfs로 하려고 하였는데 visited를 설정할 수 없어서 재귀를 쓰기 어려웠는데 답지는 bfs로 풀면서 모든 위치까지의 테이블을 반환 하여 다음에 먹을 물고기를 찾는 함수를 만들어서 하였다.
문제(19236번)
내가 푼 답
답안 예시
import copy
# 4 X 4 크기 격자에 존재하는 각 물고기의 번호(없으면 -1)와 방향 값을 담는 테이블
array = [[None] * 4 for _ in range(4)]
for i in range(4):
data = list(map(int, input().split()))
# 매 줄마다 4마리의 물고기를 하나씩 확인하며
for j in range(4):
# 각 위치마다 [물고기의 번호, 방향]을 저장
array[i][j] = [data[j * 2], data[j * 2 + 1] - 1]
# 8가지 방향에 대한 정의
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
# 현재 위치에서 왼쪽으로 회전된 결과 반환
def turn_left(direction):
return (direction + 1) % 8
result = 0 # 최종 결과
# 현재 배열에서 특정한 번호의 물고기 위치 찾기
def find_fish(array, index):
for i in range(4):
for j in range(4):
if array[i][j][0] == index:
return (i, j)
return None
# 모든 물고기를 회전 및 이동시키는 함수
def move_all_fishes(array, now_x, now_y):
# 1번부터 16번까지의 물고기를 차례대로 (낮은 번호부터) 확인
for i in range(1, 17):
# 해당 물고기의 위치를 찾기
position = find_fish(array, i)
if position != None:
x, y = position[0], position[1]
direction = array[x][y][1]
# 해당 물고기의 방향을 왼쪽으로 계속 회전시키며 이동이 가능한지 확인
for j in range(8):
nx = x + dx[direction]
ny = y + dy[direction]
# 해당 방향으로 이동이 가능하다면 이동 시키기
if 0 <= nx and nx < 4 and 0 <= ny and ny < 4:
if not (nx == now_x and ny == now_y):
array[x][y][1] = direction
array[x][y], array[nx][ny] = array[nx][ny], array[x][y]
break
direction = turn_left(direction)
# 상어가 현재 위치에서 먹을 수 있는 모든 물고기의 위치 반환
def get_possible_positions(array, now_x, now_y):
positions = []
direction = array[now_x][now_y][1]
# 현재의 방향으로 쭉 이동하기
for i in range(4):
now_x += dx[direction]
now_y += dy[direction]
# 범위를 벗어나지 않는지 확인하며
if 0 <= now_x and now_x < 4 and 0 <= now_y and now_y < 4:
# 물고기가 존재하는 경우
if array[now_x][now_y][0] != -1:
positions.append((now_x, now_y))
return positions
# 모든 경우를 탐색하기 위한 DFS 함수
def dfs(array, now_x, now_y, total):
global result
array = copy.deepcopy(array) # 리스트를 통째로 복사
total += array[now_x][now_y][0] # 현재 위치의 물고기 먹기
array[now_x][now_y][0] = -1 # 물고기를 먹었으므로 번호 값을 -1로 변환
move_all_fishes(array, now_x, now_y) # 전체 물고기 이동 시키기
# 이제 다시 상어가 이동할 차례이므로, 이동 가능한 위치 찾기
positions = get_possible_positions(array, now_x, now_y)
# 이동할 수 있는 위치가 하나도 없다면 종료
if len(positions) == 0:
result = max(result, total) # 최댓값 저장
return
# 모든 이동할 수 있는 위치로 재귀적으로 수행
for next_x, next_y in positions:
dfs(array, next_x, next_y, total)
# 청소년 상어의 시작 위치(0, 0)에서부터 재귀적으로 모든 경우 탐색
dfs(array, 0, 0, 0)
print(result)
고찰
문제(19237번)
내가 푼 답
답안 예시
n, m, k = map(int, input().split())
# 모든 상어의 위치와 방향 정보를 포함하는 2차원 리스트
array = []
for i in range(n):
array.append(list(map(int, input().split())))
# 모든 상어의 현재 방향 정보
directions = list(map(int, input().split()))
# 각 위치마다 [특정 냄새의 상어 번호, 특정 냄새의 남은 시간]을 저장하는 2차원 리스트
smell = [[[0, 0]] * n for _ in range(n)]
# 각 상어의 회전 우선순위 정보
priorities = [[] for _ in range(m)]
for i in range(m):
for j in range(4):
priorities[i].append(list(map(int, input().split())))
# 특정 위치에서 이동 가능한 4가지 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 모든 냄새 정보를 업데이트
def update_smell():
# 각 위치를 하나씩 확인하며
for i in range(n):
for j in range(n):
# 냄새가 존재하는 경우, 시간을 1만큼 감소시키기
if smell[i][j][1] > 0:
smell[i][j][1] -= 1
# 상어가 존재하는 해당 위치의 냄새를 k로 설정
if array[i][j] != 0:
smell[i][j] = [array[i][j], k]
# 모든 상어를 이동시키는 함수
def move():
# 이동 결과를 담기 위한 임시 결과 테이블 초기화
new_array = [[0] * n for _ in range(n)]
# 각 위치를 하나씩 확인하며
for x in range(n):
for y in range(n):
# 상어가 존재하는 경우
if array[x][y] != 0:
direction = directions[array[x][y] - 1] # 현재 상어의 방향
found = False
# 일단 냄새가 존재하지 않는 곳이 있는지 확인
for index in range(4):
nx = x + dx[priorities[array[x][y] - 1][direction - 1][index] - 1]
ny = y + dy[priorities[array[x][y] - 1][direction - 1][index] - 1]
if 0 <= nx and nx < n and 0 <= ny and ny < n:
if smell[nx][ny][1] == 0: # 냄새가 존재하지 않는 곳이면
# 해당 상어의 방향 이동시키기
directions[array[x][y] - 1] = priorities[array[x][y] - 1][direction - 1][index]
# 상어 이동시키기 (만약 이미 다른 상어가 있다면 번호가 낮은 것이 들어가도록)
if new_array[nx][ny] == 0:
new_array[nx][ny] = array[x][y]
else:
new_array[nx][ny] = min(new_array[nx][ny], array[x][y])
found = True
break
if found:
continue
# 주변에 모두 냄새가 남아 있다면, 자신의 냄새가 있는 곳으로 이동
for index in range(4):
nx = x + dx[priorities[array[x][y] - 1][direction - 1][index] - 1]
ny = y + dy[priorities[array[x][y] - 1][direction - 1][index] - 1]
if 0 <= nx and nx < n and 0 <= ny and ny < n:
if smell[nx][ny][0] == array[x][y]: # 자신의 냄새가 있는 곳이면
# 해당 상어의 방향 이동시키기
directions[array[x][y] - 1] = priorities[array[x][y] - 1][direction - 1][index]
# 상어 이동시키기
new_array[nx][ny] = array[x][y]
break
return new_array
time = 0
while True:
update_smell() # 모든 위치의 냄새를 업데이트
new_array = move() # 모든 상어를 이동시키기
array = new_array # 맵 업데이트
time += 1 # 시간 증가
# 1번 상어만 남았는지 체크
check = True
for i in range(n):
for j in range(n):
if array[i][j] > 1:
check = False
if check:
print(time)
break
# 1000초가 지날 때까지 끝나지 않았다면
if time >= 1000:
print(-1)
break
댓글남기기