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

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

17070번: 파이프 옮기기 1

파이프 옮기기1 문제

오늘 드디어 알고리즘 스터디를 시작하면서 백준에 있는 삼성 A형 기출 문제를 풀었다! 향후 삼성 A형 시험을 치를 예정이기 때문에 A+를 받고 싶은 마음에 (2문제중 2문제 맞추면 A+) 기출 문제 스터디를 시작했는데 아직 부족한게 많아서 생각을 코드로 옮기는게 조금은 힘들다보니 쉽게 되진 않는거 같다

100% 내 생각으로 풀었는가?
--> O

문제를 보자마자 든 생각은, 이거 DFS나 백트레킹 개념을 사용하면 편하겠다 였으나 아직 제대로 DFS와 백트레킹을 코드로 구현해본적이 없어서 사실 많이 망설여졌다. 일단 재귀 성질을 이용해 구현해보기로 해서 시도해보았다.

내가 푼 코드

import sys
N = int(sys.stdin.readline())
board = [0]*N
for new in range(N):
    board[new] = list(map(int, sys.stdin.readline().split())) #칸 만들기

cnt = 0
def searching(x,y,location): # location 기준 가로 :0 세로 : 1 대각 : 2
    global cnt
    if x == N-1 and y == N-1: # x,y 칸이 (N-1,N-1)에 도착하면 반환
        cnt += 1
        return
    if location == 0 or location == 2 : #가로나 대각으로 누워있을 때
        if y + 1 < N and board[x][y+1] == 0:  #가로로 갈 수 있다면
            searching(x,y+1,0) # 가로 증가
    if location == 1 or location == 2 : #세로나 대각으로 누워있을 떄
        if x + 1 < N and board[x+1][y] == 0: #세로로 갈 수 있다면
            searching(x+1,y,1) # 세로 증가
    if x <N-1 and y< N-1 : # 그외 가로나 세로 끝에 도착 하지 않았다면
        if board[x+1][y+1] == 0 and board[x+1][y] == 0 and board[x][y+1] == 0: #만약 가로 세로 대각이 비었다면
            searching(x+1,y+1,2) #대각선 증가

searching(0,1,0) # 시작지점 파이프 대가리 기준 0,1,0에서 시작
# 문제에 *벽*이 존재
# 벽이 그러면 도착지점에 있다면? 애초에 방법이 없으니 cnt = 0?
if board[N-1][N-1] == 1 :
    print(0)
else :
    print(cnt)

재귀를 이용해 코드를 작성하여 제출했으나 시간 초과가 떴다. 사실 백준이아니라 실제 A형 시험이었으면 무난하게 pass처리 됐을 코드라고 생각하는게 실제 A형 시험은 더 시간이 넉넉한거로 알고있다 (파이썬기준 15초정도?) 물론 시험 목적만으로 한다면 그렇지, 실제로 효율적인지 아닌지는 더 생각해봐야할 문제지만, B형부턴 메모리,시간관리가 중요하지만 A형은 그렇지 않으니 일단 pypy로 제출해보니 통과가 됐다. 

---

느낀점

골드 5수준의 문제로 내가 직접 풀어보니 평소 알고리즘 연습할 때는 시간제한 같은게 없으니까 편하고 여유롭게 이거해볼까? 저거해볼까? 시도해보면 됐는데, 막상 시간을 재고 (실제 2문제 3시간이지만 우리는 1문제 1시간으로 했다.) 문제를 푸니까 아이디어를 생각하고 구현 시도하는게 엄청나게 시간을 많이 소비하는 걸 알 수 있었다.

2문제를 해봤는데 1문제는 40%정도만 구현하고 실패해서 다시 오답노트 마냥 풀어보고 구현 시도하면서 풀어볼 생각이다. 아직은 알고리즘 초보라 그런가 갈길이 먼거같다.. 😥

그래도 조금만 노력하면 A~A+는 취득할 수 있을거 같으니 더 노력하고 정리해야겠다!

미래에 B형도 기회가 된다면 시도해보고 싶은데 B형은 python으로 못보니 나중에 java나 C++을 공부해서 한번 시도해봐야겠다!