백준 #32964 재미있는 파이프 퍼즐

문제 링크

[32964 재미있는 파이프 퍼즐]

문제 설명

$2\times N$배열이 주어지고 $(0, 0)$에서 $(1, N - 1)$칸으로 주어진 파이프들을 이용해서 갈 수 있는지 확인하는 문제

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def solve(r, c, prev_r, prev_c, cur):
    if r == 1 and c == N - 1:
        print("YES")
        exit()

    if r == 0:
        if cur == "I":
            if c + 1 < N and prev_r == 0:
                solve(r, c + 1, r, c, arr[r][c + 1])
        elif cur == "L":
            if prev_r == 0:
                solve(r + 1, c, r, c, arr[r + 1][c])
            else:
                solve(r, c + 1, r, c, arr[r][c + 1])
    elif r == 1:
        if cur == "I":
            if c + 1 < N and prev_r == 1:
                solve(r, c + 1, r, c, arr[r][c + 1])
        elif cur == "L":
            if prev_r == 0:
                solve(r, c + 1, r, c, arr[r][c + 1])
            else:
                solve(r - 1, c, r, c, arr[r - 1][c])


N = int(input())
arr = [list(input().rstrip()) for _ in range(2)]
solve(0, 1, 0, 0, arr[0][1])
solve(1, 0, 0, 0, arr[1][0])
print("NO")

풀이

파이프 모양이 I자형과 ㄱ자형 두가지이기 때문에 전에 있던 위치에 따라서 이번 파이프를 가지고 움직일 수 있는 곳이 한정적이다. I자형의 경우 무조건 옆으로만 가야하고 ㄱ의 경우에는 현재 위치와 전에 있던 위치를 고려해서 옆으로 또는 위, 아래로 갈지 결정하면 된다.