[Algorithm] BaekJoon : 17070. 파이프 옮기기 1 by Python

[문제 바로가기] https://www.acmicpc.net/problem/17070

📌문제 설명

유현이가 새 집으로 이사했다. 새 집의 크기는 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)는 항상 빈 칸이다.

입력예시
3
0 0 0
0 0 0
0 0 0
출력 : 1

💡 문제 풀이

완전탐색 + 재귀로 해결한 문제!

파이프의 이동은 가로, 세로, 대각선까지 3가지의 경우지만 각각의 이동에는 제한이 있다.
가로 ↔ 세로의 이동은 연달아서 이뤄지지 못한다는 점이다.
하지만, 대각선은 NxN 크기를 벗어나지 않는 이상 어떠한 방향이든 상관없이 연달아 진행이 가능하다.

따라서, 가로, 세로, 대각선 방향으로 파이프를 이동하기 위해서는 다음과 같이 나눌 수 있다.

1. 가로 : 현재 파이프 한쪽 끝 방향이 가로거나 대각선인 경우 진행이 가능하다.

2. 세로 : 현재 파이프 한쪽 끝 방향이 세로거나 대각선인 경우 진행이 가능하다.

3. 대각선 : 파이프 한쪽 끝이 어떠한 방향이더라도 진행이 가능하다.

또한 파이프가 1x2의 형태로 주어졌지만 파이프의 한쪽 끝이 좌측 끝에서 우측 끝지점까지 이동가능한 경로의 수만 파악하면 되기 때문에 (1, 2)지점을 기준으로 한 칸씩(가로, 세로, 대각선) 움직여 가능한 경로를 파악하면 된다.

파이프가 이동하면서 가능한 경로가 있는지 파악하기 위해 move 함수를 만들었다.

move함수에는 3개의 인자(dir, r, c)가 있다.

• dir : 파이프의 한쪽 끝 부분의 방향을 알려준다.
• r : 파이프의 행 위치(인덱스)
• c : 파이프의 열 위치(인덱스)

재귀는 도착지점(N, N)에 도달하였을 때 종료한다. 도착지점의 도달은 곧 가능한 경로를 의미하므로 answer+1을 해준다.

• answer : 도착가능한 경로의 수

앞서 가로, 세로, 대각선으로 진행할 수 있는 경우를 나누었다.

만약, 도착지점에 도달하지 않았다면 dir에 따라 가로, 세로, 대각선 방향으로 이동을 진행한다.

코드는 다음과 같다.
※ 단, PyPy3에서는 통과가 되었지만 Python3에서는 시간초과가 발생한다.

import sys

def move(dir, r, c):
    global N, answer
    if r == N-1 and c == N-1:
        answer += 1
        return
    if dir == 0 or dir == 2:      #가로
        if c+1 < N and not matrix[r][c+1]:
            move(0, r, c+1)
    if dir == 1 or dir == 2:      #세로
        if r+1 < N and not matrix[r+1][c]:
            move(1, r+1, c)
    if c+1 < N and r+1 < N:       #대각선
        if matrix[r+1][c] + matrix[r][c+1] + matrix[r+1][c+1] == 0:
            move(2, r+1, c+1)

N = int(sys.stdin.readline())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
answer = 0
move(0, 0, 1)
print(answer)

이번 문제도 시간초과가 관건이었다.
이전에는 알고리즘 구현에만 신경을 썼었는데
이제는 알고리즘과 코드 개선(최적화)까지 노력해야겠다.