[BOJ] 17070 파이프 옮기기 1

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

주어진 지형 위에서 파이프를 목적지로 옮길 수 있는 가짓수를 세는 문제.

 

1/ 조건

1) 파이프는 연속된 2칸을 차지하며, (1, 1)과 (1, 2)에 가로로 놓여 있는 채로 시작한다.

2) 파이프를 (n, n)으로 밀어서 옮겨야 한다.

3) 파이프는 회전시킬 수 있는데, 가능한 방향은 x축을 기준으로 시계방향 0도, 45도, 90도이다.

4) 지형은 0과 1로 주어지는데 0은 빈 공간, 1은 벽을 의미한다.

5) 파이프는 항상 빈칸만 차지해야 한다: 즉 벽이 있는 곳으로는 갈 수 없고, 대각선으로 놓이기 위해서는 (k, k), (k+1, k), (k, k+1), (k+1, k+1) 4칸이 전부 비어 있어야 한다.

6) 파이프는 밀면서 회전시킬 수 있는데, 현재 놓인 방향으로부터 ±45도만 회전시킬 수 있다.

 

 

2/ 설계

주어진 지형을 한 칸씩 탐색하는 형태이므로 BFS와 주어진 좌표의 인접 위치를 탐색하는 delta 방식을 사용하고 싶다고 생각했다.

만약 경우의 수가 중복된다면 그것을 따로 제해야 하는데, 이 문제의 경우에는 기존 좌표로 되돌아가는 것이 불가능하기 때문에 해당 지점은 고려하지 않아도 된다고 생각했다.

1) 파이프의 위치 2개를 전부 기록할 필요는 없다. 현재 가리키고 있는 방향과 목적지에 더 가까운 부분의 좌표만 고려하면 된다.

2) delta는 0도, 45도, 90도만을 가리키도록 설정해야 한다.

3) 현재 놓인 방향으로부터 ±45도만 회전시키는 부분을 구현해야 한다.

4) 파이프가 항상 빈칸으로만 나아갈 수 있고 동시에 빈칸만 차지해야 한다는 지점을 구현해야 한다.

 

 

3/ 구현

from collections import deque

input = __import__('sys').stdin.readline

n = int(input())
house = [list(map(int, input().rstrip().split())) for _ in range(n)]

q = deque([(0, 1, 0)])  # 가로 0, 대각선 1, 세로 2
dy = [0, 1, 1]
dx = [1, 1, 0]
cnt = 0
while q:
    ny, nx, direct = q.popleft()
    if ny == n-1 and nx == n-1:     # 도착했을 때 cnt를 1 늘려줌
        cnt += 1
    for d in range(3):
        if abs(d-direct) == 2:      # ±45만 회전 가능하도록 조건 부여
            continue
        y = ny + dy[d]
        x = nx + dx[d]
        if y < 0 or x < 0 or y >= n or x >= n:
            continue
        if d == 1 and 0 <= nx+1 < n and 0 <= ny+1 < n:      # 대각선 방향일 때 4칸이 비어 있어야 함
            if house[ny+1][nx] or house[ny][nx+1] or house[ny+1][nx+1]:
                continue
        elif house[y][x] == 1:      # 대각선 방향이 아닐 때 나아갈 방향에 벽이 없어야 함
            continue
        q.append((y, x, d))

print(cnt)

 

 

4/ 결과

시간 초과.

 

 

5/ 돌아보기

최대 16x16의 2차원 배열이 입력으로 주어지므로 해당 경우에서 모든 좌표에 대하여 (일부 중복을 포함하여) while문이 시행된다고 쳐도 연산 횟수가 많지 않을 거라고 생각했었는데 아니었나보다. 너무 rough한 계산이었을 수도 있고, Python이라 그럴지도 모르겠다.

잔가지를 쳐내봐야(예를 들어 가로인 상태로 지형의 경계선 1칸 전에 있는 경우를 배제한다거나) 의미가 없을 거라고 판단했다. 

단순히 DFS-완전탐색으로 구현할 경우 마찬가지로 시간 초과일 것이다. 백트래킹이나 일찍 cnt를 늘리는 방법이 있을까? visited 배열으로 성공한 DFS 경로를 기록하여 해당 경로에 진입할 경우 cnt를 늘리는 방식이 떠올랐는데…… 해당 지점에서 목적지로 가는 경우의 수가 몇 개인지 알아야만 하는 방법인 듯했다. 포기.

머리를 굴려봐도 답이 없어서 알고리즘 분류를 보았다. 다이나믹 프로그래밍 태그가 있었다.

생각해봤다. 다이나믹 프로그래밍이라는 분류와 DFS를 개선하려던 시도의 아이디어를 합쳐서 '임의의 좌표에 놓여 있어도 (n, n)까지 가는 문제임은 똑같은데다가 기존 좌표로 돌아가는 것이 불가능하다. DP를 사용할 수 있을 것 같긴 하다'라고 결론을 내렸다.(확신은 없었다)

 

 

6/ 재설계

2차원 dp 배열을 3개 만들어야 한다고 생각했다. 가로로 놓인 경우, 대각선으로 놓인 경우, 세로로 놓인 경우. 따라서 2차원 배열에 크기 3짜리 1차원 배열을 삽인한 3차원 배열을 사용하고자 했다.

'방향과 좌표가 주어졌을 때 어디로 갈 수 있는가'라는 조건을 '방향과 좌표가 주어졌을 때 어디에서 올 수 있는가'라는 질문으로 치환하여 조건을 재작성하였다.

 

 

7/ 구현

input = __import__('sys').stdin.readline

n = int(input())
house = [list(map(int, input().rstrip().split())) for _ in range(n)]

dp = [[[0]*3 for _ in range(n)] for __ in range(n+1)]   # 예외처리를 피하기 위해 세로 한 줄을 더 늘렸다.
dp[1][1][0] = 1

dy = [0, 1, 1]
dx = [1, 1, 0]
for i in range(1, n+1):
    for j in range(1, n):
        if house[i-1][j]:   # 해당 위치에 벽이 있는 경우. 단, dp 배열이 한 줄 더 기므로 house의 y좌표는 -1 해주어야 한다.
            continue
        for d1 in range(3):
            y = i - dy[d1]
            x = j - dx[d1]
            if d1 == 1 and (house[i-1][j-1] or house[i-2][j]):  # 대각선의 경우 위쪽과 왼쪽에 벽이 있으면 오는 것이 불가능하다.
                continue
            for d2 in range(3):
                if abs(d2-d1) < 2:  # ±45도만 고려
                    dp[i][j][d1] += dp[y][x][d2]

print(sum(dp[n][n-1]))

 

 

8/ 결과

 

야호!

 

 

9/ 후기

1) 최근에 주어진 좌표로부터 시작하여 경로를 파고 들어가며 sum의 최댓값을 구하는 문제를 풀었는데, 초기값을 0으로 주느냐 아니면 해당 좌표의 값으로 시작하느냐에 따라 시간 초과 여부가 갈렸었다. depth 하나 차이일 뿐인데도. 파이썬의 문제일까? BOJ를 비롯한 몇몇 PS 사이트가 파이썬에게 조금 너그럽지 못한 것 같기는 하다. 이렇게 다른 언어를 배워야 하는 동기가 쌓여간다.

2) '힌트가 없었다면 내가 DP를 시도할 수 있었을까?'에 대해서는 조금 회의적이다. 테스트를 보는 상황이었다면 긴장감 때문에 어떻게든 다른 방법을 사용했을 것 같기도 하지만. 첫눈에 DP가 사용 가능한지 여부를 파악하는 힘이란 무엇일까?

3) 2번에 이어서, DP란 '무엇에 의존하는가, 그 의존성을 중복된 가짓수없이 컴팩트하게 표현할 수 있는가'라고 생각한다. 아직은 잘 모르겠다. 조만간 내가 이해한 바를 정리해서 포스팅해보고자 한다. 3월 넷째 주 정도?