백준 17070번 파이프 옮기기 1 문제 풀이/코드 해설 (파이썬) 삼성 A형 기출

코드만 궁금한 분은 링크

GitHub - Rhyankwon/algorithms

 

문제 설명을 대충 하자면..

1. NxN크기의 0으로 구성된 격자가 있고, 맨 좌측 상단에 파이프가 - 방향으로 놓여져있다. [0,0], [0,1]인덱스에 있다고 생각하면편함!

2. 그 파이프의 오른쪽 끝이 격자의 가장 오른쪽 아래 [N-1, N-1]에 닿도록 파이프를 계속 움직이면 되는데..

3. 파이프가 - 방향으로 있으면 그 다음은 오른쪽 혹은 오른쪽 아래 방향으로만 이동 가능하고

   파이프가 1 방향으로 있으면 그 다음엔 아래 혹은 오른쪽 아래방향으로만 이동 가능하고,

   파이프가 대각선 (오른쪽아래)방향으로 나있으면 오른쪽/아래/오른쪽 아래 방향 세개 모두 이동가능하다.

4. 이 때, 격자에는 0만 있는게 아니라 1도 있는데, 이 부분은 피해서 파이프를 움직여야함. 1자와 -자로 파이프가 있을 땐 오른쪽 끝 부분이 1에 닿지만 않으면 되는데 대각선 모양으로 갈때에는 오른쪽 부분이 닿는 격자 및 그 왼쪽/윗쪽 격자도 모두 1이 아니어야함.

 

 

말로하니까 어려운데 이해가어려운 문제는 아니다. 나는 딱 봐도 dfs같아서 (왜냐면 문제 범위도 0~16까지로 좀 작아서 dfs로 풀면 되겠다싶었음...) dfs로 풀었는데 시간초과가 나와서...거기에서 가지치기 해본다고 이것저것 하다가 두시간 까먹고 남의 풀이 보고 풀었다.

 

다른 사람들의 풀이를 보니 파이썬은 대체로 dp를 활용해서 풀었고, 파이썬이 아닌 경우에는 시간제한에서 아무래도 조금 수월한 편이다 보니 dfs로 푼 경우도 많다.

 

물론 파이썬을 dfs로 푼 경우도 봤고 그건 내 깃허브에 가면 같이 정리돼있음. 내가 처음에 풀었다가 실행이 안됐던 코드와 그 사람 코드의 차이는, 나는 for문을 썼고 그 사람은 for문 없이 풀었다는 점정도..인데 솔직히 경우의수는 똑같이 나와서 조금 이해가 잘 안된다. 다른 사람들의 파이썬-dfs 풀이도 python3로는 해결안되고 pypy3로만 거의 간당간당하게 되는거라 아마도..내 코드에서 딕셔너리를 조금 무리하게 쓴게 문제가 아닌가 싶다. for문쓴다고 안되는건 말이안되는거같다.

 

dp풀이는 코드를 보는게 빠를 것 같다. 세로방향, 가로방향, 대각선방향 각각마다 각 격자에 갈 수 있는 경우의 수가 있는데, 다음 격자의 경우의 수는 이전 격자의 경우의 수에서 가능한 방향 들의 합이다. dp로 풀면 어려울줄알았는데 처음에 세로방향, 가로, 대각선 방향 각각의 경우의 수를 따로 구하고 더할땐 또 같이 활용한다는 점만 잘 캐치하면 된다.