[알고리즘 문제 풀이🙄] 1861. 정사각형 방

📌 문제 요약

N^2개의 방이 NxN 형태로 늘어서 있을 때, 각 방에는 숫자가 기입되어 있다. 출발점에서 상하좌우의 다른 방으로 이동이 가능할 때, 이동하려는 방에 적힌 숫자는 현재 방에 적힌 숫자보다 정확히 1만큼 더 커야 한다. 이때 처음 어떤 수가 적힌 방에 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하라. (각 방에 기입된 숫자는 1부터 N^2까지이다.)

 

😖 내가 생각한 로직

• [잘못된 로직] 백트래킹 활용 방법
  1. 방에 적힌 숫자들을 입력받을 때, enumerate를 사용하여 후에 방 번호를 계산할 수 있도록 한다.
  2. 입력받은 방 정보 리스트를 순회하며 백트래킹을 활용하여 이동 횟수가 최대가 되는 출발지점(방)을 찾는다.
     → 즉, 모든 방에서 출발해서 최대한 이동해보는 방법

 

😥 틀린 코드와 문제점

• DFS(백트래킹)로 구현

# DFS
def dfs(si, sj, visited, moving):
    global mx_moving, sx, sy

    bf_moving = mx_moving
    visited[si][sj] = True
    mx_moving = max(mx_moving, moving)
    
    if mx_moving != bf_moving:
        sx = si 
        sy = sj

    for d in directions:
        mi = si + d[0]
        mj = sj + d[1]

        if 0 <= mi < N and 0 <= mj < N:
            if not visited[mi][mj] and rooms[mi][mj][1] - rooms[si][sj][1] == 1:
                moving += 1
                dfs(mi, mj, visited, moving)
                visited[mi][mj] = False
                moving -= 1


# 상 하 좌 우
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

T = int(input())

for tc in range(1, T + 1):
    N = int(input())
    rooms = [list(enumerate(map(int, input().split()))) for _ in range(N)]
    mx_moving = 0           # 방문한 최대 개수의 방
    sx = sy = 0             # 최대 개수의 방을 방문할 때의 출발점
    
    for i in range(N):
        for j in range(N):
            visited = [[False] * (N) for _ in range(N)]
            dfs(i, j, visited, 0)
    
    print(f'#{tc} {sx * N + (rooms[sx][sy][0] + 1)} {mx_moving}')

 

▷ 답도 틀리고 'RecursionError: maximum recursion depth exceeded in comparison' 에러도 난다.

 

• 나름대로 강사님 코드를 참고하여 다시 작성한 코드 (근데도 틀렸다😥)

# 상 하 좌 우
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

T = int(input())

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

    # 1부터 N ** 2를 인덱스로 갖는 배열 생성
    visited = [0] * (N ** 2 + 1)
    # 숫자 i의 인접(상하좌우)에 1 큰 수가 존재하는 경우 index[i]에 1 표시
    idx = 0
    for i in range(N):
        if i % 2 == 0:
            rs = 0
            re = N
            rt = 1
        else:
            rs = N - 1
            re = -1
            rt = -1

        for j in range(rs, re, rt):
            idx += 1
            for d in directions:
                mi = i + d[0]
                mj = j + d[1]
                if 0 <= mi < N and 0 <= mj < N:
                    if rooms[mi][mj] - rooms[i][j] == 1:
                        visited[idx] = 1
                        break

    mx_len = mx_room = 0
    length = start = 1

    # 1이 최대로 연속하는 길이를 찾음
    for k in range(1, N ** 2):
        if visited[k] == 1:
            length += 1
        else:
            if mx_len < length:
                mx_len = length
                # start 말고 방에 적힌 수를 읽어와야 함
                i = (start - 1) // N
                if i % 2 == 0:          # 짝수 행일 때,
                    j = start - N * i - 1
                else:                   # 홀수 행일 때,
                    j = i * N - (start - N)
                mx_room = rooms[i][j]
            start = k + 1
            length = 1

    print(f'#{tc} {mx_room} {mx_len}')

 

▶ 해당 코드의 문제점이 무엇인지는 모르겠으나, 문제를 잘못 이해한 것이라는 걸 한참 후에야 알았다.

 NxN 형태의 방들의 값이 1 ~ N^2 의 값으로 이루어져있고, 내가 도출해야 하는 결과값이 '어떤 수가 적힌 방에서 시작해야 가장 많은 개수의 방을 이동할 수 있는지'와 '최대로 이동할 수 있는 방의 개수'라는 걸 '몇 번째 방에서 시작해야 가장 많은 개수의 방을 이동할 수 있는지'와 '최대로 이동할 수 있는 방의 개수'인 것으로 잘못 이해했다.

 

→ 따라서 올바른 결과값을 도출하려면 visited[num]에 표시하는 것을 'num = (방의 순서)'가 아니라 'num = (그 방에 적힌 수)'로 진행해야 한다.

 

 

🤗 제출 후 pass한 코드

# 상 하 좌 우
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

T = int(input())

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

    # 1부터 N^2까지를 인덱스로 갖는 배열 생성
    visited = [0] * (N ** 2 + 1)
    for i in range(N):
        for j in range(N):
            for d in directions:
                mi = i + d[0]
                mj = j + d[1]
                if 0 <= mi < N and 0 <= mj < N:
                    if rooms[mi][mj] - rooms[i][j] == 1:
                        visited[rooms[i][j]] = 1
                        break               # 하나라도 존재하는지만 확인

    mx_len = mx_room = 0
    length = start = 1

    # 1이 최대로 연속하는 길이를 찾음
    # 방에 적힌 값의 범위: 1 ~ N^2
    for k in range(1, N ** 2 + 1):
        if visited[k] == 1:
            length += 1
        else:
            if mx_len < length:
                mx_len = length
                mx_room = start
            start = k + 1
            length = 1

    print(f'#{tc} {mx_room} {mx_len}')

 

🧐 참고할 코드

• (DFS 활용) 모든 방에서 출발해 최대한 이동해 보는 방안
  → 다행히 이 문제에서는 시간 초과가 발생하지 않았지만, 조금만 복잡한 테스트 케이스가 추가되면 바로 터질 것 같다고 강사님이 설명하신 접근법이다.

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

def DFS(sy, sx):
    global board, cnt
    for i in range(4):
        ny, nx = sy + dy[i], sx + dx[i]
        if 0 <= ny < N and 0 <= nx < N:
            if board[ny][nx] == board[sy][sx] + 1:
                cnt += 1
                DFS(ny, nx)


T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    max_cnt, resulty, resultx = 0, 0, 0
    for y in range(N):
        for x in range(N):
            cnt = 1
            DFS(y, x)
            if max_cnt < cnt:
                max_cnt = cnt
                resulty = y
                resultx = x
            elif max_cnt == cnt and board[y][x] < board[resulty][resultx]:
                resulty = y
                resultx = x

    print(f'#{tc} {board[resulty][resultx]} {max_cnt}')

 

•  뭐라고 설명을 적어야 할지 모르겠다🙄❓

# 접근방법2
# 1. 전체 배열을 순회하면서 확인한다.
# 2. 인접한 방의 숫자가 현재 방보다 1 크면 visited 1 체크
#  - 1이 크면 다음으로 갈 수 있다
# -> 정리: 다음으로 갈 수 있는 방이다 라는 정보를 저장

T = int(input())

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

for tc in range(1, T + 1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    # index 에러 조심!
    visited = [0] * (N * N + 1)
    
    # 전체를 순회하며
    # 상하좌우에 나보다 1이 크다면, visited 체크
    for i in range(N):
        for j in range(N):
            for k in range(4):
                # ny, nx = 다음 좌표
                ny = i + dy[k]
                nx = j + dx[k]

                # 범위 체크
                if ny < 0 or ny >= N or nx < 0 or nx >= N:
                    continue

                # 내 옆이 나보다 1 크다면, 나는 다음으로 갈 수 있는 방이다.
                if arr[ny][nx] == arr[i][j] + 1:
                    visited[arr[i][j]] = 1
                    # 이미 체크된 순간, 다른 방향은 볼 필요가 없음
                    # 이유: 동일한 숫자가 없기 때문
                    break

    # cnt: 하나씩 체크 / max_cnt: 정답(최대값) / start: 계산을 시작할 위치
    cnt = max_cnt = start = 0

    for i in range(N * N - 1, -1, -1):
        if visited[i]:
            cnt += 1
        else:
            if max_cnt <= cnt:
                max_cnt = cnt
                start = i + 1
            cnt = 0  # cnt 초기화

    print(f'#{tc} {start} {max_cnt + 1}')

 

 

😎 앞으로의 개선 방향

어제(9/5) 현대 소프티어 역량 테스트를 하면서 문제를 풀기 전에 로직을 꼼꼼히 세우고 했더니 문제가 술술 풀리는 경험을 했다. (아쉽지만 시간복잡도를 고려하지 못해 아마 통과는 못했을 것 같다ㅜ) 그래서 오늘도 그렇게 접근했는데, 이번엔 입력되는 값을 꼼꼼히 체크하지 못해 문제 이해를 다르게 해버리는 이슈가 발생했다. 아직 나는 갈 길이 많이 멀다는 것을 또 한번 느낀 경험이었다. 문제 푸는 습관을 하나씩 고쳐나가야겠다. 

 

시간을 많이 잡아먹었지만, 그래도 끝내 이해해내서 다행이다. 하지만 처음 로직을 짤 때 접근법이 잘못된 문제점도 있으니, 이 부분을 유의하면서 다음 문제 풀이 때는 좀더 꼼꼼히 로직을 점검해보고 작성해야겠다.