[SWEA] 1861 정사각형 방 Python

[ 문제 ]

 

난이도:  D4

문제 번호:  1861

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE&problemTitle=1861&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

---

 

N2개의 방이 N×N형태로 늘어서 있다.

위에서 i번째 줄의 왼쪽에서 j번째 방에는 1이상 N2 이하의 수 Ai,j가 적혀 있으며,

이 숫자는 모든 방에 대해 서로 다르다.

당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다.

물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다.

처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램을 작성하라.

 

---

 

[ 코드 ]

def find(r, c, cnt):
    global max_count
    stack = [(r, c, cnt)]
    while stack:
        cr, cc, ccnt = stack.pop()
        for k in range(4):
            nr = cr + dr[k]
            nc = cc + dc[k]
            if 0<=nc<N and 0<=nr<N and rooms[cr][cc] + 1 == rooms[nr][nc]:
                stack.append((nr, nc, ccnt+1))
                break
    if ccnt >= max_count:
        max_count = ccnt
        cnt_li.append((rooms[r][c], ccnt))
 
for tc in range(1, int(input())+1):
    N = int(input())
    rooms = [list(map(int, input().split())) for _ in range(N)]
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    max_count = 0
    min_num = 987654321
    cnt_li = []
    for i in range(N):
        for j in range(N):
            find(i, j, 0)
 
    for i in range(len(cnt_li)):
        if cnt_li[i][1] == max_count:
            if cnt_li[i][0] < min_num:
                min_num = cnt_li[i][0]
    print('#{} {} {}'.format(tc, min_num, max_count+1))