[문제풀이-백준] 17070. 파이프 옮기기1
파이프 옮기기 1
처음 생각했던 아이디어
- 가로,세로,대각선 정보에 따라 다음에 갈 수 있는 곳을 다시 각각 가로,세로,대각선 함수를 이용하여 해결하려고 했음
- 0%에서 시간 초과 발생
그 다음 생각했던 아이디어
- 이미 들어온 곳에 다른 경로나 막대 방향으로 들어온다면 원래 있던 가짓 수에서 들어온 가짓 수를 더하면 된다고 생각
- 들어올때의 막대 방향에 따라 갈 수 있는 경우의 수가 모두 다르므로 불가능
개선한 아이디어
-
가로,세로,대각선 함수를 각각 만드는 것이 아니라 bfs 함수 하나만을 이용하여 탐색한다.
-
가능한 방향에는 deque에 y,x뿐만 아니라 방향 정보도 넣어줌
-
넣어준 방향에 따라 다시 갈 수 있는 방향 탐색
-
도착지점에 도착하면 갯수 + 1
-
시간 초과 0%
개선한 아이디어(2)
- 위 bfs를 재귀함수를 이용한 dfs로 바꿔줌
- 통과
결론
- deque를 이용하더라도 bfs보다는 재귀의 dfs가 빠름
코드
- python
def dfs(y,x,shape):
global cnt
if y == N-1 and x == N-1:
cnt += 1
return
if shape == 0:
if x + 1 < N and not matrix[y][x+1]:
dfs(y,x+1,0)
if y + 1 < N and x + 1 < N and not matrix[y+1][x+1] and not matrix[y][x+1] and not matrix[y+1][x]:
dfs(y+1,x+1,2)
elif shape == 1:
if y + 1 < N and not matrix[y+1][x]:
dfs(y+1,x,1)
if y + 1 < N and x + 1 < N and not matrix[y+1][x+1] and not matrix[y][x+1] and not matrix[y+1][x]:
dfs(y+1,x+1,2)
elif shape == 2 :
if x + 1 < N and not matrix[y][x+1]:
dfs(y,x+1,0)
if y + 1 < N and not matrix[y+1][x]:
dfs(y+1,x,1)
if y + 1 < N and x + 1 < N and not matrix[y+1][x+1] and not matrix[y][x+1] and not matrix[y+1][x]:
dfs(y+1,x+1,2)
N = int(input())
matrix = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
dfs(0,1,0)
print(cnt)
Author And Source
이 문제에 관하여([문제풀이-백준] 17070. 파이프 옮기기1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@psj8532/문제풀이-백준-17070.-파이프-옮기기1
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
처음 생각했던 아이디어
- 0%에서 시간 초과 발생
그 다음 생각했던 아이디어
- 들어올때의 막대 방향에 따라 갈 수 있는 경우의 수가 모두 다르므로 불가능
개선한 아이디어
가로,세로,대각선 함수를 각각 만드는 것이 아니라 bfs 함수 하나만을 이용하여 탐색한다.
가능한 방향에는 deque에 y,x뿐만 아니라 방향 정보도 넣어줌
넣어준 방향에 따라 다시 갈 수 있는 방향 탐색
도착지점에 도착하면 갯수 + 1
시간 초과 0%
개선한 아이디어(2)
결론
코드
def dfs(y,x,shape):
global cnt
if y == N-1 and x == N-1:
cnt += 1
return
if shape == 0:
if x + 1 < N and not matrix[y][x+1]:
dfs(y,x+1,0)
if y + 1 < N and x + 1 < N and not matrix[y+1][x+1] and not matrix[y][x+1] and not matrix[y+1][x]:
dfs(y+1,x+1,2)
elif shape == 1:
if y + 1 < N and not matrix[y+1][x]:
dfs(y+1,x,1)
if y + 1 < N and x + 1 < N and not matrix[y+1][x+1] and not matrix[y][x+1] and not matrix[y+1][x]:
dfs(y+1,x+1,2)
elif shape == 2 :
if x + 1 < N and not matrix[y][x+1]:
dfs(y,x+1,0)
if y + 1 < N and not matrix[y+1][x]:
dfs(y+1,x,1)
if y + 1 < N and x + 1 < N and not matrix[y+1][x+1] and not matrix[y][x+1] and not matrix[y+1][x]:
dfs(y+1,x+1,2)
N = int(input())
matrix = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
dfs(0,1,0)
print(cnt)
Author And Source
이 문제에 관하여([문제풀이-백준] 17070. 파이프 옮기기1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@psj8532/문제풀이-백준-17070.-파이프-옮기기1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)