[백준 17070번] 파이프 옮기기 1(파이썬)

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

17070번: 파이프 옮기기 1

이 문제는 문제자체보다는

문제가 길어서

'이게 뭔소리야...'

하면서 문제를 이해하는 게 좀 걸렸습니다.

(워낙 문제가 길어서)

 

이 문제는 구현만 잘 시켜주면 됩니다.

가로 세로 대각선

각각을 움직일 때

어떻게 움직일지 제대로 구현만 해주면 끝.

 

#
# from collections import deque
# N=int(input())
# room=[list(map(int,input().split())) for _ in range(N)]
# visited=[[0]*N for _ in range(N)]
#
# da=[[0,1],[1,1],[1,0]]
#
# q=deque()
# q.append([0,1,'g'])
#
# while q:
#     pos_x,pos_y,con=q.popleft()
#     #가로
#     now_x=pos_x
#     now_y=pos_y
#     if con=='g':
#         #가로로 이동할 경우
#         if pos_y+1<N and room[pos_x][pos_y+1]==0:
#             now_x=pos_x
#             now_y=pos_y+1
#             visited[now_x][now_y]+=1
#             q.append([now_x,now_y,'g'])
#         #대각선 아래로 이동할 경우
#         if pos_x+1<N and pos_y+1<N:
#             go=True
#             for i in range(3):
#                 go_x,go_y=da[i]
#                 if room[pos_x+go_x][pos_y+go_y]==1:
#                     go=False
#                     break
#             if go==False:
#                 continue
#             now_y=pos_y+1
#             now_x=pos_x+1
#             visited[now_x][now_y]+=1
#             q.append([now_x,now_y,'d'])
#
#     #세로
#     elif con=='s':
#         #세로로 이동할 경우
#         if pos_x+1<N and room[pos_x+1][pos_y]==0:
#             now_x=pos_x+1
#             now_y=pos_y
#             visited[now_x][now_y]+=1
#             q.append([now_x,now_y,'s'])
#         #대각선으로 이동하는 경우
#         if pos_x+1<N and pos_y+1<N:
#             go=True
#             for i in range(3):
#                 go_x,go_y=da[i]
#                 if room[pos_x+go_x][pos_y+go_y]==1:
#                     go=False
#                     break
#             if go==False:
#                 continue
#
#             now_y=pos_y+1
#             now_x=pos_x+1
#             visited[now_x][now_y]+=1
#             q.append([now_x,now_y,'d'])
#     #대각선
#     elif con=='d':
#         #가로로 이동
#         if pos_y+1<N and room[pos_x][pos_y+1]==0:
#             now_x=pos_x
#             now_y=pos_y+1
#             visited[now_x][now_y]+=1
#             q.append([now_x,now_y,'g'])
#         #세로로 이동
#         if pos_x+1<N and room[pos_x+1][pos_y]==0:
#             now_x=pos_x+1
#             now_y=pos_y
#             visited[now_x][now_y]+=1
#             q.append([now_x,now_y,'s'])
#         #대각선으로 이동
#         if pos_x+1<N and pos_y+1<N:
#             go=True
#             for i in range(3):
#                 go_x,go_y=da[i]
#                 if room[pos_x+go_x][pos_y+go_y]==1:
#                     go=False
#                     break
#             if go==False:
#                 continue
#             now_y=pos_y+1
#             now_x=pos_x+1
#             visited[now_x][now_y]+=1
#             q.append([now_x,now_y,'d'])
#
# print(visited[N-1][N-1])

 

 

이건 BFS로 풀이한 코드입니다.

이 코드로 제출하면 

pypy3로 제출해도

63%대에서 시간초과가 발생합니다.

질문하기를 눌러보니

BFS로 제출하면

시간초과가 뜨는데

DFS로 제출하면 시간초과가 안뜬다고 나옵니다.

왜 이런 차이가 생길지 고려해보면

bfs시 더 많은 경우를 탐색할 수 있어서

라는 생각입니다.

 

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

def dfs(x,y,d):
    global result
    if x==N-1 and y==N-1:
        result+=1
        return
    #d의 상태는 현재 가로/세로/대각선인지 파악
    #가로 0 세로 1 대각선 2

    #가로로 이동
    if d==0 or d==2:
        ny=y+1
        if ny<N and room[x][ny]==0:
            dfs(x,ny,0)
    #세로로 이동
    if d==1 or d==2:
        nx=x+1
        if nx<N and room[nx][y]==0:
            dfs(nx,y,1)
    #대각선으로 이동
    nx=x+1
    ny=y+1
    if nx<N and ny<N and room[nx][ny]==0 and room[nx][y]==0 and room[x][ny]==0:
        dfs(nx,ny,2)

if room[N-1][N-1]==1:
    print(0)
else:
    dfs(0,1,0)
    print(result)

이렇게 DFS로 구현하면

pypy기준으로 통과합니다.

 

https://pacific-ocean.tistory.com/458

[백준] 17070번(python 파이썬)

https://backtony.github.io/algorithm/2021-03-02-algorithm-boj-class4-44/

(Python) 백준 17070번 파이프 옮기기1 - class 4

이 문제는 dp로도 풀 수 있다고 나오네요.

백준 알고리즘 분류상에

다이나믹 프로그래밍도 포함이 되어있는 걸 보면

이런 풀이도 가능한 모양입니다만...

dp풀이가 익숙하지 않으면

구현이 쉽지 않겠네요.

dp를 공부하는 의미로 보면 좋을듯합니다.