SWEA 1861번: 정사각형 방 (D4) - Python 풀이

문제 설명

SW Expert Academy

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

위에서 i번째 줄의 왼쪽에서 j번째 방에는 1 이상 N2 이하의 수 Ai,j가 적혀 있으며, 이 숫자는 모든 방에 대해 서로 다르다.

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

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

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

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (1 ≤ N ≤ 103)이 주어진다.

다음 N개의 줄에는 i번째 줄에는 N개의 정수 Ai, 1, … , Ai, N (1 ≤ Ai, j ≤ N2) 이 공백 하나로 구분되어 주어진다.
Ai, j는 모두 서로 다른 수이다.

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 한 칸을 띄운 후, 처음에 출발해야 하는 방 번호와 최대 몇 개의 방을 이동할 수 있는지를 공백으로 구분하여 출력한다.

이동할 수 있는 방의 개수가 최대인 방이 여럿이라면 그 중에서 적힌 수가 가장 작은 것을 출력한다.

입력

2
2
1 2
3 4
3
9 3 4
6 1 5
7 8 2

input.txt

출력

#1 1 2
#2 3 3

output.txt

[예제 풀이]

첫 번째 테스트 케이스는 1 또는 3이 적힌 곳에 있어야 한다.
두 번째 테스트 케이스는 3 또는 6이 적힌 곳에 있어야 한다.

풀이 과정

어떤 방에서 시작해야 가장 많은 개수의 방을 이동할 수 있는지 구해야 합니다.

그렇다면 가능한 모든 방에서 이동을 시작해서 몇 개의 방을 이동했는지 저장해두고, 그 값을 최대로 만드는 방의 번호를 알면 됩니다.

상하좌우로 이동 가능하니까 방향 벡터 4개를 사용하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 1만큼 더 클 때, 그 방으로 이동해서 더이상 이동할 방이 없을 때까지 탐색합니다. 그때까지 이동한 방의 개수를 시작점의 방 번호와 함께 배열 answers에 저장해두면, 모든 시작점을 확인한 후에 answers를 정렬해서 답을 구할 수 있습니다.

정답 코드

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
	  
    # 방에 적힌 숫자 입력
    rooms = [[] for _ in range(N)]
    for i in range(N):
        rooms[i] = list(map(int, input().split()))
     
    answers = []
    # 이동한 방의 개수
    rooms_num = 0
    
    # (start_x, start_y) 위치에서 상하좌우 이동해서 rooms_num 값을 업데이트
    def recursive(start_x, start_y):
        global rooms_num
        # 이동한 방의 개수 rooms_num의 카운트를 증가
        rooms_num += 1
				
        # (start_x, start_y) 좌표의 상하좌우
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        for d in range(4):
            # 새 좌표
            nx = start_x + dx[d]
            ny = start_y + dy[d]
            # (nx, ny)가 유효한 범위 내의 좌표이고, (start_x, start_y) 위치의 방에 적힌 숫자보다 1 크다면
            if 0 <= nx < N and 0 <= ny < N and rooms[nx][ny] == rooms[start_x][start_y] + 1:
                # (nx, ny)에서 다시 탐색 (= (nx, ny)로 이동했다는 뜻)
                recursive(nx, ny)
		
    # 가능한 모든 시작점에서 탐색
    for x in range(N):
        for y in range(N):
            # (x,y) 위치의 방에서 이동을 시작할 때 몇 개의 방을 이동할 수 있는지 확인
            recursive(x, y)
            # 재귀 함수를 통해 이동한 방의 개수 rooms_num를 구해서
            # answers에 시작점의 방 번호와 이동한 방의 개수를 튜플로 묶어 append
            answers.append((rooms[x][y], rooms_num))
            # 이동한 방의 개수 초기화
            rooms_num = 0
            
    # 이동한 방의 개수를 기준으로 내림차순 정렬을 하되, 이 값이 같다면 방에 적힌 숫자를 기준으로 오름차순 정렬
    answers.sort(key=lambda x: (-x[1], x[0]))
	  
    # 정렬된 배열에서 맨 앞 값을 가져와 방에 적힌 숫자(방 번호)와 이동한 방의 개수를 출력
    print("#%d" % test_case, answers[0][0], answers[0][1])

answers를 정렬할 때 1순위로 이동한 방의 개수를 기준으로 내림차순 정렬을 했지만, 문제의 조건대로 이동할 수 있는 방의 개수가 최대인 방이 여럿이라면 방 번호가 가장 작은 것을 출력할 수 있게 방 번호의 오름차순 정렬을 2순위로 두었습니다.

또한 이 문제의 경우 재귀 함수를 통해 DFS의 로직으로 구현하지만 visited 배열을 쓰지 않습니다. (여기서 visited 배열을 사용하면 O(N²)의 추가 메모리가 필요하며, 재귀 호출마다 체크해야 해서 시간 복잡도가 증가합니다.) 처음에 풀 때 이것을 모르고 visited 배열을 두어 시간 초과가 났습니다.

쓰지 않아도 되는 이유는, 1) 모든 방의 숫자는 서로 다르고, 2) 이동 조건이 현재 방 숫자 + 1인 방으로만 이동할 수 있기 때문입니다. 이로 인해 경로는 A → A+1 → A+2 → … 처럼 항상 한쪽으로 증가합니다. 즉, 역방향 이동이 불가능 = 이미 지나간 방으로 되돌아갈 수 없어서 중복 방문이 발생하지 않습니다.

이상입니다.