(python) 7562 나이트의 이동, 7569 토마토

7562 나이트의 이동

https://www.acmicpc.net/problem/7562

문제

체스판의 길이와 시작위치, 도착위치를 주고

체스에서의 나이트로 최소 몇 번만에 도착할 수 있을지 묻는 문제이다.

 

입력

테스트 케이스 개수를 주고

그다음 

체스판의 한 변의 길이 (체스판은 주어진 변수 * 변수가 크기가 된다.)

시작위치 x, y

도착위치 x, y

 

기본적인 그래프에서의 BFS를 사용하고 이동 좌표만 나이트에 맞추어 설정해 주면 된다.

from collections import deque

def bfs():
  while queue:
    x, y = queue.popleft()
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < length and 0 <= ny < length: #범위 제한
        if chess[nx][ny] == 0:
          chess[nx][ny] = chess[x][y] + 1
          queue.append((nx, ny))
        
n = int(input()) #테스트 케이스 갯수
chess = []
# 나이트가 이동하는 좌표로 설정 총 8개
dx = [2, 2, -2, -2, 1, -1, 1, -1]
dy = [1, -1, 1, -1, 2, 2, -2, -2]

for i in range(n):
  length = int(input())
  chess = [[0 for i in range(length)] for j in range(length)]
  now_x, now_y = map(int, input().split())
  t_x, t_y = map(int, input().split())
  if (now_x, now_y) == (t_x, t_y):
    print(0)
  else:
    queue = deque()
    queue.append((now_x, now_y))
    bfs()
    print(chess[t_x][t_y])
  chess = []

---

7569 토마토

https://www.acmicpc.net/problem/7569

이 문제는 7576 토마토 문제의 심화 버전이다.

7576 토마토는 한 판만 문제로 주어졌지만

7569 토마토 문제는 여러 개의 토마토 판이 주어지면서 z 축까지 고려해야 된다.

 

익은 토마토가 영향을 미치는 방향이 상하좌우 위아래로 바뀌었다.

1은 익은 토마토, 0은 일반 토마토, -1은 벽으로 동일하다.

 

여러 층이 존재하다 보니 이중리스트로 풀기 벅차다.

삼중리스트로 하면 생각하기도 풀기도 편하다.

 

7576 토마토 문제에서 z 축만 추가해 주면 문제 해결이다.

import sys
from collections import deque

def bfs():
  while queue:
    z, x, y = queue.popleft()
    for i in range(6): # 위 아래 경우 포함
      nx = x + dx[i]
      ny = y + dy[i]
      nz = z + dz[i]
      # z의 경우 높이 h를 넘기면 안된다.
      if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h and tomato[nz][nx][ny] == 0:
        tomato[nz][nx][ny] = tomato[z][x][y] + 1
        queue.append((nz, nx, ny))
m, n, h = map(int, input().split())
tomato = [[] for _ in range(h)] # 판이 갯수대로 이중리스트 만들기
for i in range(h): # 각 판에 맞추어 넣어준다
  for j in range(n):
    tomato[i].append(list(map(int, sys.stdin.readline().split())))
queue = deque()
for i in range(h):
  for j in range(n):
    for k in range(m):
      if tomato[i][j][k] == 1:
        queue.append((i, j, k))
# dz를 추가해서 z축까지
dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]
bfs()
result = 0
for i in tomato: # 삼중리스트에 맞추어 반복문을 하나 더 만듬
  for j in i:
    for k in j:
      if k == 0:
        print(-1)
        exit(0)
    result = max(result, max(j))
print(result - 1)