[Python] 17070 파이프 옮기기 1

📌 문제

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

가로

세로

대각선

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

📌 입력

첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

📌 출력

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.

📌 문제 풀이

👨‍🏫 접근

이 문제는 재귀를 통한 DFS를 통해서 풀 수도 있고, 동적 프로그래밍으로도 풀 수 있다.

먼저 재귀를 통한 풀이는 코드 구현이 간단하다. 각 파이프가 이동할 수 있는 조건들을 받아서 입력하여 재귀적으로 함수를 호출하면 된다.

예를 들어 가로로 놓인 파이프가 있고 그때의 좌표가 x, y라고 한다면, x, y + 1 좌표에 벽이 있는지 확인하고 가로로 이동하는 방법과 x, y + 1/x + 1, y/x + 1, y + 1에 벽이 있는지 확인하여 대각선으로 이동하는 방법 두 가지가 있다.

더 간단하게 세 가지 이동(가로, 세로, 대각선)에 대한 방향 조건을 세우고, 그 이동을 할 수 있는 방향으로 놓인 파이브일 때 재귀 함수를 호출하는 것이다.

import sys
n = int(sys.stdin.readline())
graph = [['0'] * (n + 2) for _ in range(n + 2)]

for i in range(1, n + 1):
    graph[i][1:-1] = sys.stdin.readline().rstrip().split()

if graph[n][n] == '1':
    print(0)
    exit()

ans = 0

# 0 = 가로, 1 = 대각선, 2 = 세로
def pipe(x, y, direction):
    global ans

    if x > n or y > n:
        return

    if x == n and y == n:
        ans += 1

    if graph[x + 1][y] != '1' and (direction == 1 or direction == 2):
        pipe(x + 1, y, 2)

    if graph[x + 1][y + 1] != '1' and graph[x + 1][y] != '1' and graph[x][y + 1] != '1':
        pipe(x + 1, y + 1, 1)

    if graph[x][y + 1] != '1' and (direction == 1 or direction == 0):
        pipe(x, y + 1, 0)

pipe(1, 2, 0)

print(ans)

코드를 더 쉽게 풀이하기 위해서 행과 열 끝에 각각 한 줄을 더해서 행의 개수와 열의 개수를 2개 씩 늘렸다.

물론 이렇게 풀이하는 것도 틀린 방법은 아니다. 하지만, 재귀함수로 구현을 해보니 각 함수가 세 번씩 자기 자신을 실행하기 때문에 시간 복잡도가 굉장히 크게 나온다. 아마도 세 번씩 실행하다보니 O(3ⁿ)의 시간 복잡도가 소요되지 않을까 싶다!

그래서 시간 복잡도를 확 줄일 수 있는 방법으로 동적 프로그래밍을 실시하는 방법이 있다. 먼저 파이프의 진행 방향은 좌상우하로만 이동하기 때문에 분기가 적은 편이며, 이동한 횟수가 그 이전 파이프에서 온 횟수에 추가적으로 더해지기 때문에 테이블을 생성하여 동적으로 정보를 저장하며 활용하는 것이 가능하다.

예를 들어, (x, y) 좌표가 끝부분이고 가로 방향으로 놓인 경우에는 (x, y - 1)(2차원 리스트로 생각했을 때의 좌표) 좌표에서 가로 방향으로 왔거나 대각선 방향으로 온 것이다.

가로 방향이 아니라 세로 방향이었을 경우에는 (x - 1, y) 좌표에서 세로 방향으로 왔거나 혹은 대각선 방향으로 온 것이다.

대각선 방향이었을 경우에는 (x - 1, y - 1) 좌표에서 가로·세로·대각선 방향으로 온 것이다.

이것을 보면 방향을 0, 1, 2로 나눈 다음에 3차원 리스트로 DP 테이블을 만든 다음에 풀 수 있음을 짐작할 수 있다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline

n = int(input())
house = [list(map(int, input().split())) for _ in range(n)]
pipe = [[[0, 0, 0] for _ in range(n)] for _ in range(n)]
pipe[0][1][0] = 1
for i in range(1, n - 1):
    if house[0][i + 1]:
        break
    pipe[0][i + 1][0] = pipe[0][i][0]
for i in range(1, n):
    for j in range(1, n):
        if house[i][j]:
            continue
        pipe[i][j][0] = pipe[i][j - 1][0] + pipe[i][j - 1][1]
        pipe[i][j][2] = pipe[i - 1][j][1] + pipe[i - 1][j][2]
        if house[i - 1][j] or house[i][j - 1]:
            continue
        pipe[i][j][1] = sum(pipe[i - 1][j - 1])
print(sum(pipe[n - 1][n - 1]))

📄 준비

import sys
input = sys.stdin.readline

n = int(input())
house = [list(map(int, input().split())) for _ in range(n)]
pipe = [[[0, 0, 0] for _ in range(n)] for _ in range(n)]
pipe[0][1][0] = 1
for i in range(1, n - 1):
    if house[0][i + 1]:
        break
    pipe[0][i + 1][0] = pipe[0][i][0]

입력이 많으므로 sys 모듈의 readline 메서드를 사용한다.

house는 파이프가 놓일 맵의 좌표이다.

pipe 테이블은 3차원 리스트로 만들어준다. 일단 맵을 사용하기에 2차원 리스트로 구성한 다음, 각 방향에 따라 값이 또 달라지기 때문에 3차원 리스트로 구조를 형성했다.

이때, 항상 파이프는 가로 방향으로 놓여 (1, 1), (1, 2)에 놓이기 때문에 pipe[0][1][0]에는 1 을 넣어준다. pipe리스트에서 방향을 0이 가로, 1이 세로, 2가 대각선이라고 가정한다.

파이브가 가로로 놓였을 때 가로 방향으로 쭉 이동하는 것은 항상 한 가지 경우 밖에 없으므로 매번 값을 갱신해준다. 굳이 매번 갱신하는 이유는 벽이 있어서 가로 막히면 그 이후로 나아가지 못하는 경우가 있기 때문에 매번 값을 갱신한다. 이때, 벽이 쳐져있으면 바로 반복문을 탈출한다.

for 반복문에서 range가 1부터 시작하는 이유는 pipe[0][0][0]이 0이며 pipe[0][1][0]이 1이라서 값을 유지시키기 위함이다.

📄 풀이

for i in range(1, n):
    for j in range(1, n):
        if house[i][j]:
            continue
        pipe[i][j][0] = pipe[i][j - 1][0] + pipe[i][j - 1][1]
        pipe[i][j][2] = pipe[i - 1][j][1] + pipe[i - 1][j][2]
        if house[i - 1][j] or house[i][j - 1]:
            continue
        pipe[i][j][1] = sum(pipe[i - 1][j - 1])
print(sum(pipe[n - 1][n - 1]))

pipe 값들이 이전 좌표를 참고하기 때문에 i와 j 반복문의 시작은 1부터 시작하도록 한다. 벽이 쳐져있는 경우는 제외한다.

먼저 가로 방향으로 진행하는 파이프인 경우

pipe[i][j][0] = pipe[i][j - 1][0] + pipe[i][j - 1][1]

이전에 가로 방향이었던 파이프와 대각선 방향이었던 파이프가 가지고 있는 값을 더한다.

세로 방향으로 진행하는 파이프인 경우

pipe[i][j][2] = pipe[i - 1][j][1] + pipe[i - 1][j][2]

이전에 세로 방향이었던 파이프와 대각선 방향이어떤 파이프가 가지고 있는 값을 더한다.

대각선 방향으로 진행하는 파이프인 경우

if house[i - 1][j] or house[i][j - 1]:
    continue
pipe[i][j][1] = sum(pipe[i - 1][j - 1])

끝 좌표를 기준으로 위와 왼쪽에 파이프가 없어야 하므로 그 경우를 제외한 다음, 모든 방향에서 오는 파이프는 대각선으로 이동할 수 있기 때문에 이전 대각선 좌표에서 sum을 통해 값을 갱신하도록 한다.

📌 총평

오랜만에 재미있는 문제를 발견했다!

재귀도 연습하면서 시간 복잡도도 배웠고 동적 프로그래밍에 대해서도 배웠다.