[백준 17070] 파이프 옮기기 1

 

1. 문제

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

2. 접근방법

파이프의 모양마다 붙일 수 있는 파이프의 종류가 다른 점에서 시작 !

 

N이 작아서 완탐 문제라고 생각했음

1. 가로 파이프의 경우

가로 OR 대각선만 가능

 

1-1. 가로 파이프를 끼우기 위해서는

 

오른쪽만 확인하면 됨

 

1-2. 대각선 파이프를 끼우기 위해서는

 

오른쪽, 아래쪽, 대각선 아래 확인하면 됨

 

2. 세로 파이프의 경우

 

세로 OR 대각선만 가능

 

2-1. 세로 파이프를 끼우기 위해서는

 

아래를 확인하면 됨

 

2-2. 대각선 파이프를 끼우기 위해서는

 

오른쪽, 아래쪽, 대각선 아래 확인하면 됨

 

3. 대각선 파이프의 경우

 

가로 OR 세로 OR 대각선 가능

 

3-1. 가로 파이프를 끼우기 위해서는 

 

오른쪽 확인

 

3-2. 세로 파이프를 끼우기 위해서는

 

아래 확인

 

3-3. 대각선 파이프를 끼우기 위해서는

 

대각선 아래 확인

 

3. 파이썬 코드

def ispipe(x, y, pipe):
    global ans, N
    if x == N-1 and y == N-1:
        ans += 1

    if pipe == 0:
        if x+1 < N and board[y][x+1] != 1:
            ispipe(x+1, y, 0)
            if y+1 < N and board[y+1][x] != 1 and board[y+1][x+1] != 1:
                ispipe(x+1, y+1, 2)
    elif pipe == 1:
        if y+1 < N and board[y+1][x] != 1:
            ispipe(x, y+1, 1)
            if x+1 < N and board[y][x+1] != 1 and board[y+1][x+1] != 1:
                ispipe(x+1, y+1, 2)
    elif pipe == 2:
        if x+1 < N and board[y][x+1] != 1:
            ispipe(x+1, y, 0)
        if y+1 < N and board[y+1][x] != 1:
            ispipe(x, y+1, 1)
            if x+1 < N and board[y][x+1] != 1 and board[y+1][x+1] != 1:
                ispipe(x+1, y+1, 2)

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
ans = 0

ispipe(1, 0, 0)
print(ans)

 

4. 마치며

 

DP 문제라고 하는데 ..

 

겹치는 조건을 한칸 들여써서 중복체크안하고 ...pypy3로 해서 ..시간초과 안났다 ... 8ㅅ8

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

사실 처음에는 지금 현재 파이프 기준으로 해서 더 짧게 코드 짜갔는데 중복 체크하기 때문에 시간 초과 났다.

 

그리고 하늘쓰가 고런식으로 짜지 말라고 했다 ^^*ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

습관을 잘못 들인 탓입니다요 ..

 

여튼무튼 내일 다시 DP로 다시 풀어보는 것으로 하고 여기서 끄읏

 

아 참 그리고 방문 여부 체크 안하는 이유는

 

무조건 오른쪽, 아래로 방향이 정해져있기 때문에 방문 여부 체크는 필요 없습니다~!

 

그럼 이만 ~!