문제 링크
https://www.acmicpc.net/problem/17069
https://www.acmicpc.net/problem/17070
문제 링크
n=int(input())
board=[list(map(int,input().split())) for _ in range(n)]
dp=dict()
def checked(nx1,ny1,nx2,ny2):
global board
if nx2<0 or ny2<0 or nx2>=n or ny2>=n:
return False
if abs(nx1-nx2)==1 and abs(ny1-ny2)==1:
if nx2-1<0 or nx2-1>=n or ny2-1<0 or ny2-1>=n:
return False
if board[nx2-1][ny2]==1 or board[nx2][ny2-1]==1:
return False
if board[nx2][ny2]==1:
return False
return True
def dfs(x1,y1,x2,y2):
if x2==n-1 and y2==n-1:
dp[(x1,y1,x2,y2)]=1
return dp[(x1,y1,x2,y2)]
if (x1,y1,x2,y2) in dp:
return dp[(x1,y1,x2,y2)]
dp[(x1,y1,x2,y2)]=0
if abs(x1-x2)==1 and abs(y1-y2)==1:
for dx1,dy1,dx2,dy2 in [(1,1,1,1),(1,1,1,0),(1,1,0,1)]:
nx1,ny1,nx2,ny2=x1+dx1,y1+dy1,x2+dx2,y2+dy2
if not checked(nx1,ny1,nx2,ny2):
continue
dp[(x1,y1,x2,y2)]+=dfs(nx1,ny1,nx2,ny2)
elif abs(y1-y2)==1:
for dx1,dy1,dx2,dy2 in [(0,1,0,1),(0,1,1,1)]:
nx1,ny1,nx2,ny2=x1+dx1,y1+dy1,x2+dx2,y2+dy2
if not checked(nx1,ny1,nx2,ny2):
continue
dp[(x1,y1,x2,y2)]+=dfs(nx1,ny1,nx2,ny2)
elif abs(x1-x2)==1:
for dx1,dy1,dx2,dy2 in [(1,0,1,0),(1,0,1,1)]:
nx1,ny1,nx2,ny2=x1+dx1,y1+dy1,x2+dx2,y2+dy2
if not checked(nx1,ny1,nx2,ny2):
continue
dp[(x1,y1,x2,y2)]+=dfs(nx1,ny1,nx2,ny2)
return dp[(x1,y1,x2,y2)]
answer=0
answer=dfs(0,0,0,1)
print(answer)파이프 이동 경로 찾기: 모든 방법을 찾아라! 🚰🔍
파이프를 특정한 방향으로 옮기는 모든 방법을 찾는 문제이다. 각 방법으로 나아갈 수 있는 모든 방법으로 뻗어나가면서 찾기 때문에 DFS를 생각할 수 있고 이 수를 줄이기 위해 이것에 DP를 도입을 할 생각을 할 수 있다.
먼저 DFS의 틀을 만들어준다. 현 좌표에 따라 나아갈 수 있는 좌표 방향의 종류가 있고 이 종류에 따라 또 DFS를 수행할 수 있다. 그렇기 때문에 현재 상황을 if문으로 분류하고 이 안에서 나아갈 수 있는 좌표의 방향을 나누어 들어간다. 이때, 나아가는 방향이 전부 오른쪽, 아래, 오른쪽 아래 이므로 파이프를 이루는 끝 좌표만 확인하면 된다. 이 이동이 가능한지 check하는 로직이 같기 때문에 이를 따로 빼두었다.
이동이 가능한지 전부 체크하면서 결과적으로 n-1,n-1 좌표에 도달하면 정답에 1을 더해주는 DFS를 완성시킨다. 이제 이것을 탐색했던 경로는 다시 탐색하지 않아도 되게 dp로 둘 수 있다. 상황이 복잡하므로 현재 상황 좌표 자체를 dp로 두기 위해 dict을 이용하였고 만약 dp가 존재한다면 이미 그 경로로 가본거기 때문에 return한다. 만약 경로가 없다면 현재 dp를 구하는 과정이기 때문에 현재 dp를 dict에 생성해주고 경로 값들을 더해서 현재 dp를 만들어줌과 동시에 return 시킨다.
이렇게 Python으로 백준의 "파이프 옮기기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
