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

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

17070번: 파이프 옮기기 1

 

1. 난이도 골드5 (🥇)

 

이제 삼성문제 풀 수 있지 않을까? 생각하고 시도한 오만방자한 과거의 나 눈감아

 

테스트케이스를 모두 맞아서 신나게 제출했지만 70% 에서 계속 시간초과가 떴다.

 

결국 구글로 도망갔고 다른 사람들의 코드와 비교해보니 시간초과가 뜰 만 했다는 생각,, 반성하게 되는 하루

 

(우울해져서 SWEA 가입하고 왔음)

 

2. 내가 작성한 코드 (70%에서 시간초과)

from collections import deque
import sys

input = sys.stdin.readline
n = int(input().rstrip()) #집의 크기

house = [list(map(int, input().rstrip().split())) for _ in range(n)]


def bfs():

  cnt = 0 #가능한 방법의 수
  queue = []
  queue = deque()
  queue.append((0,1,"x"))

  while queue:

    x,y,state = queue.popleft()

    if (x,y) == (n-1,n-1):
      cnt+=1

    if state == "x": #가로
      dx = [0,1]
      dy = [1,1]

      for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx<0 or ny<0 or nx>=n or ny>=n:
          continue
        
        if i == 0: #가로로 움직임
          if 1 in (house[nx][ny],house[nx][ny-1]):
            continue
          else:
            queue.append((nx,ny,"x"))

        elif i == 1: #대각선으로 움직임
          if 1 in (house[nx][ny], house[nx-1][ny], house[nx][ny-1], house[nx-1][ny-1]):
            continue
          else:
            queue.append((nx,ny,"z"))

    elif state == "y": #세로
      dx = [1,1]
      dy = [0,1]
      
      for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx<0 or ny<0 or nx>=n or ny>=n:
          continue
      
        if i == 0: #세로로 움직임
          if 1 in (house[nx][ny],house[nx-1][ny]):
            continue
          else:
            queue.append((nx,ny,"y"))
        
        elif i == 1: #대각선으로 움직임
          if 1 in (house[nx][ny], house[nx-1][ny], house[nx][ny-1], house[nx-1][ny-1]):
            continue
          else:
            queue.append((nx,ny,"z"))
    

    elif state == "z": #대각선
      dx = [0,1,1]
      dy = [1,0,1]

      for i in range(3):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx<0 or ny<0 or nx>=n or ny>=n:
          continue
      
        if i == 0: #가로로 움직임
          if 1 in (house[nx][ny],house[nx][ny-1]):
            continue
          else:
            queue.append((nx,ny,"x"))

        elif i == 1:
           if 1 in (house[nx][ny],house[nx-1][ny]):
            continue
           else:
            queue.append((nx,ny,"y"))

        elif i == 2:
          if 1 in (house[nx][ny], house[nx-1][ny], house[nx][ny-1], house[nx-1][ny-1]):
            continue
          else:
            queue.append((nx,ny,"z"))

  return cnt


if house[n-1][n-1] == 1:
  print(0)
else:
  print(bfs())

우선 BFS로 시도해봤다.

 

처음 상태가 가로인 경우, 세로인 경우, 대각선인 경우를 각각 나누고,

 

가로(가로, 대각선) / 세로(세로, 대각선) / 대각선(가로, 세로, 대각선)

 

위와 같이 각각의 움직임 하나하나를 queue에 넣으며 문제를 풀었다.

 

즉, 중복되는 연산이 엄청나게 많았다.

 

3. 정답 코드

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

n = int(input().rstrip()) #집의 크기

house = [list(map(int, input().rstrip().split())) for _ in range(n)]


def dfs(x,y,state):
  global cnt

  if x == n-1 and y == n-1:
    cnt+=1

  #대각선 이동
  if x+1<n and y+1<n:
    if house[x+1][y] == 0 and house[x+1][y+1] == 0 and house[x][y+1]== 0:
      dfs(x+1,y+1,"z")

  #가로 이동
  if state == "x" or state == "z":
    if y+1<n:
      if house[x][y+1] == 0:
        dfs(x,y+1,"x")
        
  #세로 이동
  if state == "y" or state == "z":
    if x+1<n:
      if house[x+1][y] == 0:
        dfs(x+1,y,"y")

#도착점에 벽이 있을 경우
if house[n-1][n-1] == 1:
  print(0)
else:
  cnt = 0
  dfs(0,1,"x")
  print(cnt)

 

생각1) 중복된 연산 줄이기

 

1. 첫 상태가 대각선인 경우 가로, 세로, 대각선 이동을 모두 해봐야 한다.

2. 첫 상태가 가로 or 대각선인 경우 가로로 이동을 할 수 있다.

3. 첫 상태가 세로 or 대각선인 경우 세로로 이동할 수 있다.

 

위와 같이 이동 연산으로 dfs를 돌리며 중복된 내용을 지웠다. 

 

이렇게 연산으로 중복을 최소화하면 nx<0, ny<0, nx>=n, ny>=n을 체크할 필요 없다.

미는 방향이 오른쪽, 아래, 오른쪽 대각선이기때문에 0보다 작은지는 당연히 확인할 필요가 없고,

최종 이동할 좌표 (대각선의 경우 x+1, y+1)가 벽을 넘지 않는지만 확인하면 된다.

 

 

생각2) 이동한 좌표는 빈 칸임이 보장됨

 

house[nx][ny], house[nx-1][ny], house[nx][ny-1], house[nx-1][ny-1]

 

내가 처음 제출한 코드 중 일부이다. 대각선으로 이동할 경우 이동 후 좌표를 포함하여 네 군데를 확인한 후, 모두 벽이 아니면 dfs 연산을 실행했다. 그러나  이동 전 좌표값은 빈 칸으로 보장이 되어있기 때문에 불필요하게 확인할 필요가 없다.

 

 

생각3) 완전탐색으로 풀어야 할 경우 범위가 작으면 dfs, 크면 dp

참고링크 : https://backtony.github.io/algorithm/2021-03-02-algorithm-boj-class4-44/

 

파이썬은 느린 언어이다. queue는 같은 정점을 여러 번 방문하고, visit라는 list를 만들기 때문에 DFS보다 느리다고 한다. 따라서 완전탐색으로 풀어야 할 경우엔 DFS를 선택해야하고, 너무 데이터가 크면 DP를 선택하자.

 

생각4) 도착점에 벽이 있을 경우 dfs 연산을 할 필요가 없음

 

메모

처음으로 삼성문제를 도전해봤으나, 크게 데이고(7시도, 7실패) 다시 정진해야함을 깨달았다.

 

우선, 그동안 너무 정형화된 풀이에 집착하면서 최적화를 생각하지 않았음이 분명하다..

 

중복되는 연산을 피하고, 시간복잡도를 고려하는 훈련을 계속 해야겠다.