💡 문제 해결
- 최초에 출발의 방 번호는 가장 큰 수로 설정하고, 이동할 수 있는 방의 개수는 최소로 설정
- 모든 방 하나하나에 대해 탐색
stack을 통해 4방탐색하여 자신의 방보다 1크면 stack에 추가- 탐색을 마친 후 방 번호와 이동할 수 있는 방의 개수를 비교
📌 시간초과가 날 줄 알았던 문제이지만 시간초과가 나지 않아 생각보다 쉽게 풀었던 문제
📌 N ** 2 크기의 리스트를 만들어 이동할 수 있는 방의 개수를 저장하여 max를 통해 구하는 방법도 가능!
🧾 문제 설명
※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.
N2개의 방이 N×N형태로 늘어서 있다.
위에서 i번째 줄의 왼쪽에서 j번째 방에는 1이상 N2 이하의 수 Ai,j가 적혀 있으며,
이 숫자는 모든 방에 대해 서로 다르다.
당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다.
물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다.
처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램을 작성하라.🖨 입출력
📝 풀이
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
def search(start):
global N
cnt = 0
stack = [start]
while stack:
x, y = stack.pop()
cnt += 1
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < N:
if arr[x][y] + 1 == arr[nx][ny]:
stack.append((nx, ny))
return cnt
for tc in range(1, int(input()) + 1):
N = int(input())
arr = list(list(map(int, input().split())) for _ in range(N))
answer = [float('inf'), 0]
for i in range(N):
for j in range(N):
cnt = search((i, j))
if cnt > answer[1]:
answer[1] = cnt
answer[0] = arr[i][j]
elif cnt == answer[1]:
if arr[i][j] < answer[0]:
answer[0] = arr[i][j]
print(f'#{tc} {answer[0]} {answer[1]}')
Impossible + 땀 한방울 == I'm possible