[Python, 파이썬] SWEA 1861. 정사각형 방

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

 

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

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

 

이동할 수 있는 방의 수가 가장 많은 방의 번호는?

 

 

 

def Get():
    A = [[0 for i in range(N+2)]] # 수열 A

    # 수열 입력받기
    for i in range(N):
        A.append([0]+list(map(int, input().split()))+[0])

    A.append([0 for i in range(N+2)])

    return A

def Graph(A):
    
    next_room = [[] for i in range(N*N+1)]

    for i in range(1, N+1):
        for j in range(1, N+1):
            
            v = A[i][j] # 현재 블록
            next_ = next((num for num in [A[i][j-1], A[i][j+1], A[i-1][j], A[i+1][j]] if num == A[i][j] + 1), 0) # 갈 수 있는 블록

            next_room[v]= next_ # 다음 room 저장

    return next_room

def DFS(i, dep):

    global max_depth

    if(room[i]): # 탐색한 room이면 더 이상 탐색 x
        max_depth = dep+room[i]-1 # 메모이제이션 사용해 최대값 구함
        return

    max_depth = max(max_depth, dep) # 최대 깊이 갱신
    
    if(next_room[i]): # 다음 room이 있으면
        DFS(next_room[i], dep+1) # 연결된 room 탐색

T = int(input()) # 테스트케이스 수 T

for test_case in range(1, T+1):

    N = int(input()) # 정수 N

    A = Get() # 수열 입력받기     
    next_room = Graph(A) # 경로 배열 생성

    room = [0]*(N*N+1) # 최대 이동할 수 있는 방의 개수를 저장해 둔 배열
    
    # 탐색 시작
    for i in range(N*N, 0, -1):
        max_depth = 1
        DFS(i, 1) # 최대 방 개수 계산
        room[i] = max_depth # 방 업뎃

    # 가장 최대인 방 탐색
    max_index = room.index(max(room)) 
            
    print("#%d %d %d" %(test_case, max_index, room[max_index]))    

 

 

 

 

[문제풀이]

---

 

와.... 이 문제 장난 아니였다.

D4를 처음 풀어보는 데 5-6시간은 걸렸다.

막상 풀고 나니 코드가 좀 간단한데 처음 푸는 거라 무척 헤맸다:(

 

우선 입력받은 배열 요소의 상하좌우를 검사하기 위해 이렇게 0으로 이루어진 한겹 패딩을 쳐줬다.

 

 

그 후 이렇게 배열 요소 하나하나 상하좌우를 검사해 갈 수 있는 다음번 room이 있는지 검사해줬다.

현재 room +1 번째 room으로만 갈 수 있기 때문에 있으면 다음번 room 번호, 없으면 0을 넣어줬다.

 

그 다음 DFS으로 최대 갈 수 있는 경로를 확인만 해주면 된다.

if(next_room[i]): # 다음 room이 있으면
    DFS(next_room[i], dep+1) # 연결된 room 탐색

 

 

연결된 다음 room이 있을 시 이동하고, 연결된 방의 개수를 +1 해주면 된다.

그러나 경로를 일일이 다 확인하면 시간 초과가 난다. 그래서 메모이제이션을 이용해 시간 단축을 해줘야 한다.

if(room[i]): # 탐색한 room이면 더 이상 탐색 x
    max_depth = max(dep+room[i], max_depth) # 최대값 갱신
    return    

 

최대 이동할 수 있는 방의 개수를 저장해 둔 room 배열을 확인해 이미 탐색한 방일 시 그 값을 이용해 시간 단축!

그럼 시간 내에 문제 없이 문제를 pass 할 수 있다.