2/17 Coding Test

✅ 문제 풀이

🎈 7576 토마토

가로, 세로 길이가 각각 M, N인 그래프가 주어지고 그래프 내 0, 1, -1이 주어진다. 0은 익지 않은 토마토, 1은 익은 토마토, -1은 빈 칸을 의미하는데, 전체 그래프에 있는 토마토가 모두 익을 때까지 걸린 날짜를 출력하는 문제

from collections import deque
import sys
input = sys.stdin.readline
# 가로 세로, 입력값 받기
m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
queue = deque()
# 4방향 상하좌우 지정
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 익은 토마토 있는 곳 모두 queue에 넣기
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append((i, j))
def bfs():
	# 큐 빌 때까지 반복
    while queue:
        x, y = queue.popleft()
        # 4방향 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 주어진 범위 내 다음 칸이 익지 않은 토마토인 경우
            if 0<=nx<n and 0<=ny<m:
                if graph[nx][ny] == 0:
                	# 익은 날짜들 다음 값으로 저장 및 큐에 삽입
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx, ny))
day = 0
bfs()
# 그래프 내 행마다
for i in graph:
	# 각 행의 값마다
    for j in i:
    	# 시작 칸이 -1인 경우 탈출
        if j == 0:
            print(-1)
            exit(0)
    # 아니면 각 행의 최대값과 day 비교
    day = max(day, max(i))
# 익은 토마토는 1부터 시작하므로 -1 해주기
print(day-1)

< 풀이 과정 >
BFS를 이용하였고, 익은 토마토가 있는 모든 위치를 큐에 표시해준다. 이후 BFS 탐색을 진행하여 주어진 범위 내 다음 방문 값이 익지 않은 토마토인 경우 큐에 삽입 후 다음 칸 값 = 현재 값 + 1 진행
주어진 그래프 내 모든 행의 데이터 각 값을 체크하여 0이 있는 경우 -1 칸이 있던 것이므로 -1을 출력하고 EXIT진행 (이를 안해주면 시간 초과)
이외는 day와 비교하여 더 큰 값을 출력해준다

🎈 7569 토마토

이번엔 앞선 문제에 3차원으로 구성해 기존 m, n에 상자 수 H가 추가되었다.

from collections import deque
import sys
input = sys.stdin.readline

# 가로 세로 상자수, 토마토, 방문 여부 만들기
m, n, h = map(int, input().split())
tomato = [[list(map(int, input().rstrip().split())) for _ in range(n)] for _ in range(h)]
visited = [[[False]*m for _ in range(n)] for _ in range(h)]
queue = deque()
# 앞뒤 상하 좌우
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
day = 0

def bfs():
	# 큐 빌때까지
    while queue:
        x, y, z = queue.popleft()
        # 6방향 탐색
        for i in range(6):
            nx = x+dx[i]
            ny = y+dy[i]
            nz = z+dz[i]
            # 주어진 범위 내 방문하지 않고 다음 칸이 익지 않은 토마토 있는 경우
            if 0<=nx<h and 0<=ny<n and 0<=nz<m and visited[nx][ny][nz] == False:
                if tomato[nx][ny][nz] == 0:
                	# 큐에 삽입, 다음 값 + 1, 방문 처리
                    queue.append((nx, ny, nz))
                    tomato[nx][ny][nz] = tomato[x][y][z] + 1
                    visited[nx][ny][nz] = True

for i in range(h):
    for j in range(n):
        for r in range(m):
            if tomato[i][j][r] == 1 and visited[i][j][r] == False:
                queue.append((i,j,r))
                visited[i][j][r] = True
bfs()
# 토마토 내 ROW 들 중 각 값을 체크하고 각 데이터 범위만큼 0인 것 발견하면 EXIT
for i in tomato:
    for j in i:
        for r in j:
            if r == 0:
                print(-1)
                exit(0)
        day = max(day, max(j))
# 익은 토마토므로 1부터 시작하니 -1해주기
print(day-1)

< 풀이 과정 >
앞선 문제를 3차원으로 풀어낸 BFS 문제. 문제 풀이 방식은 앞선 문제와 동일하고, 단지 방향이 추가되어 확인해준다.

🎈 16236 아기 상어

NXN 크기의 공간에 물고기 M마리와 아기 상어가 1마리 있다. 아기 상어의 크기는 2이고 자신보다 작은 크기의 물고기만 먹을 수 있다.
아기상어가 이동할 수 있는 방법은 다음과 같다

• 더 이상 먹을 물고기 없으면 엄마 상어에게 도움 요청
• 먹을 수 있는 물고기가 1마리보다 많으면 가장 가까운 물고기 먹기(위, 왼쪽 순서로)
  이때 아기상어가 엄마상어에게 도움 요청하지 않고 물고기를 먹을 수 있는 시간을 출력하기
  핵심은 아기상어는 자신의 크기와 같은 수의 물고기를 먹어야 크기가 1 증가한다.

from collections import deque
import sys
input = sys.stdin.readline
# n, 그래프를 입력받아 시작점이 9인 곳의 좌표와 그래프에 상어 크기 표시하기
n = int(input())
graph = []
for i in range(n):
    row = list(map(int, input().split()))
    graph.append(row)
    for j in range(n):
        if row[j] == 9:
            graph[i][j] = 2
            start = [i, j]
# 상하좌우 4방향 탐색
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(i, j):
	# 방문 처리 여부 그래프 생성
    visited = [[0]*n for _ in range(n)]
    # 시작점 방문 처리
    visited[i][j] = 1
    queue = deque()
    # 큐에 현위치 삽입
    queue.append((i, j))
    # 최소 거리 그래프로 작성 
    dist = [[0]*n for _ in range(n)]
    # 상어가 먹은 물고기의 좌표, 거리 리스트로 저장
    eat = []
    while queue:
        x, y = queue.popleft()
        # 4방향 탐색
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            # 다음 칸이 범위내에 있고 방문하지 않았다면,
            if 0<=nx<n and 0<=ny<n and not visited[nx][ny]:
                # 다음 칸이 0이거나 현재 상어 크기가 더 크면 
                if not graph[nx][ny] or graph[nx][ny] <= graph[i][j]:
                	방문 처리하고 거리 + 1, 큐에 삽입
                    visited[nx][ny] = 1
                    dist[nx][ny] = dist[x][y] + 1
                    queue.append((nx, ny))
                # 다음 칸이 0이 아닌 물고기고 현재 상어 크기보다 작으면 먹기
                if graph[nx][ny] < graph[i][j] and graph[nx][ny]:
                    eat.append((nx, ny, dist[nx][ny]))
    # 먹은게 없으면 -1 리턴
    if not eat:
        return -1, -1, -1
    # 먹은게 있다면 거리 오름차순, y, x좌표 순서대로 오름차순 정렬후 첫 값 리턴
    eat.sort(key = lambda x: (x[2], x[0], x[1]))
    return eat[0][0], eat[0][1], eat[0][2]

answer = 0
size = 0
while True:
	# 초기값 저장
    i, j = start[0], start[1]
    # 초기값 기준 bfs 탐색해 처음 먹은 물고기 나온 경우부터 탐색
    x, y, dist = bfs(i, j)
    # 먹은게 없다면 중단,
    if x == -1:
        break
    # 상어 다음 위치로 이동 후 0으로 변경
    graph[x][y] = graph[i][j]
    graph[i][j] = 0
    # 초기값 바꿔주고 먹은 횟수 증가
    start = [x, y]
    size += 1
    먹은 수가 상어크기와 같으면 먹은 횟수 초기화, 상어크기 +1
    if size == graph[x][y]: 
        size = 0
        graph[x][y] += 1
    answer += dist
print(answer)

< 풀이 과정 >
BFS로 풀이했고, 오랜만에 풀었지만 구현에 시간이 걸린 문제. 생각해야할 부분이 한 두개가 아니었다.

• 입력값
  그래프 크기 n을 입력받아 그래프를 만들고 입력받은 그래프의 위치가 9인 곳을 찾아 해당 위치의 좌표를 시작점인 start 변수로 두고 그래프에는 상어크기를 매핑시킨다
• BFS 함수
  방문여부, 거리여부를 따지는 2차원 리스트를 만들고 큐가 빌때까지 반복시키는데, 주어진 그래프 내 범위와 방문하지 않은 곳에 한해 다음 두가지 조건을 거쳐 탐색한다.
  1) 현 상어의 크기가 이동한 칸 값보다 크거나 같고 혹은 다음 위치에 물고기가 없는 경우, 큐에 삽입하고 방문처리, 거리 + 1 진행
  2) 현 상어의 크기가 이동한 칸 값보다 크고 다음 위치에 물고기가 있는 경우, eat이라는 물고기를 먹은 리스트에 (좌표, 거리)정보를 저장한다
  먹은게 없다면 -1을 리턴하고, 거리, 위, 왼쪽 순서대로 가까운 물고기를 먹으므로 정렬 후 가장 가까운 곳의 물고기를 리턴하여 먹은 곳의 좌표를 리턴한다.
• while 반복문을 이용하여 시작점으로부터 bfs 탐색으로 나온 물고기 먹은 곳의 좌표를 찾고 상어가 이동했으므로 그래프 내 값 변화시켜주고, 자신의 크기만큼 물고기를 먹어야 상어크기가 커지므로 size라는 변수를 활용하여 상어크기를 키워준다.
  최종적으로 이동한 거리만큼 더해 출력한다.