https://www.acmicpc.net/problem/17070
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
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실패) 다시 정진해야함을 깨달았다.
우선, 그동안 너무 정형화된 풀이에 집착하면서 최적화를 생각하지 않았음이 분명하다..
중복되는 연산을 피하고, 시간복잡도를 고려하는 훈련을 계속 해야겠다.
댓글