SWEA_1861_정사각형 방

아이디어 1

• 각 칸에서 재귀함수 사용해 이동한 칸 수 세기

  • N이 최대 1000, N x N인 경우 최대 1000000칸 이동 가능

  • 가능한 재귀호출 회수

    • python3 대략 1000
    • pypy3.6 대략 2300

  • 재귀함수 사용 불가!

  • 다른 방법을 사용해야겠다.

• 반복을 이용한 탐색을 진행해야겠네

• 각 자리에서 탐색을 진행

  • 가지치기

    • 탐색했던 기록을 저장하여 시작점이 탐색한 적이 있었다면 탐색을 진행하지 않는 것으로 해도 되지 않을까?

    • 탐색했던 기록이 그 지점을 시작으로 하는 "경로의 길이"라면, 탐색 중에 해당 지점을 도착하더라도 탐색을 중복하여 할 필요가 없지 않을까?
      (이 방법은 쉽지 않았다.)

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

def search(r, c, count):
    stack = [(r, c, count)]
    while stack:
        cr, cc, c_count = stack.pop()

        for di in range(4):
            nr = cr + dr[di]
            nc = cc + dc[di]
            if 0 <= nr < N and 0 <= nc < N:
                if BOARD[nr][nc] == BOARD[cr][cc] + 1:
                    stack.append((nr, nc, c_count + 1))
                    # 모든 수는 서로 다르기 때문에, 갈 수 있는 방향도 한 곳 밖에는 없다.
                    break
        # 모든 방향을 탐색했지만 갈 수 있는 곳이 없었다.
        else:
            if c_count != 1:
                start_memory[BOARD[r][c]] = c_count

T = int(input())

for tc in range(1, T + 1):
    # N: 배열의 크기
    N = int(input())
    # 탐색할 배열
    BOARD = [list(map(int, input().split())) for _ in range(N)]

    # 탐색했던 칸을 저장하는 배열
    # 이 칸으로 부터
    start_memory = [0] * (N * N)
    for i in range(N):
        for j in range(N):
            search(i, j, 1)

    # 저장한 배열 중 가장 큰 값을 갖고 있는 가장 작은 인덱스를 찾는다.
    max_length = max(start_memory)
    result = start_memory.index(max_length)
    print(f"#{tc} {result} {max_length}")

아이디어 2

• N * N까지의 인덱스를 가진 1차원 배열을 만들어 0으로 초기화한다.

• 모든 칸을 순회한다

  • 주위를 탐색하여, 나보다 1 큰 값을 가진 칸이 있으면 그 칸의 값을 인덱스로 하는 배열의 칸을 1로 저장한다.

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

def search(sr, sc):
    for di in range(4):
        nr = sr + dr[di]
        nc = sc + dc[di]
        if 0 <= nr < N and 0 <= nc < N:
            if BOARD[sr][sc] + 1 == BOARD[nr][nc]:
                can_progress[BOARD[sr][sc]] = True
                break

T = int(input())

for tc in range(1, T + 1):
    N = int(input())

    BOARD = [list(map(int, input().split())) for _ in range(N)]

    # 숫자는 1부터 시작한다.
    # 마지막 숫자는 자기보다 큰 숫자가 없기 때문에 사실 1을 더해주지 않아도 된다.
    # can_progress = [False] * ((N * N) + 1)
    can_progress = [False] * (N * N)

    for i in range(N):
        for j in range(N):
            search(i, j)

    # print(can_progress)
    # can_progress를 역순으로 탐색하여, 숫자를 셉니다.
    max_number = N * N
    max_length = 0
    count = 1
    for i in range((N * N) - 1, 0, -1):
        if can_progress[i]:
            count += 1
            if not can_progress[i - 1]:
                if max_length <= count:
                    max_length = max(max_length, count)
                    max_number = i
                count = 1
    print(f"#{tc}", max_number, max_length)