[python] SWEA - 1861. 정사각형 방

🤔문제 해결

1. D4 | DFS

2. 선택한 숫자와 +1, -1로 연결될 수 있는 구간을 찾는 방법을 사용

3. 처음 숫자를 선택하고 그 숫자보다 값이 1이 큰 숫자를 계속 찾는다

4. 그 숫자보다 값이 1이 작은 숫자도 계속 찾는다.

5. 찾은 작은 숫자 ~ 큰 숫자의 범위가 하나의 구간이 된다.

6. 값을 다른 숫자(ex. -10)으로 바꿔줘서 하나의 구간을 여러번 탐색하지 않게 한다.

7. 모든 구간들을 구하고 구간의 길이가 가장 긴 구간을 선택. 구간이 여러개라면 시작점이 가장 작은 숫자를 선택한다.

 (cnt_list는 시작점을 인덱스로 하고 값을 구간의 길이로 하는 리스트이다)

 

💨 하나하나 모든 숫자를 탐색해도 되지만 효율이 좋지 않을 것 같다.

 

💻소스 코드

 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

for tc in range(1, 1+int(input())):
    n = int(input())
    maps = [list(map(int, input().split())) for _ in range(n)]

    cnt_list = [0] * (n ** 2 + 1)

    for i in range(n):
        for j in range(n):
            if maps[i][j] > 0:
                low_stack = [(i, j)]
                low_num = maps[i][j]

                high_num = maps[i][j]
                high_stack = [(i, j)]

                maps[i][j] = -10
                # 큰 숫자 찾기
                while high_stack:
                    x, y = high_stack.pop()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if 0<=nx<n and 0<=ny<n:
                            if maps[nx][ny] == high_num + 1:
                                high_stack.append((nx,ny))
                                high_num += 1
                                maps[nx][ny] = -10
                                break
                # 작은 숫자 찾기
                while low_stack:
                    x, y = low_stack.pop()

                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if 0<=nx<n and 0<=ny<n:
                            if maps[nx][ny] == low_num - 1:
                                low_stack.append((nx,ny))
                                low_num -= 1
                                maps[nx][ny] = -10
                                break

                cnt_list[low_num] = high_num - low_num + 1

    max_cnt = max(cnt_list)
    max_cnt_idx = cnt_list.index(max_cnt)
    print('#{} {} {}'.format(tc, max_cnt_idx, max_cnt))

 

📕문제 확인

출처: SW Expert Academy

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE

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부터 시작한다)를 출력하고,

한 칸을 띄운 후, 처음에 출발해야 하는 방 번호와 최대 몇 개의 방을 이동할 수 있는지를 공백으로 구분하여 출력한다.

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


[예제 풀이]

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

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