티스토리 뷰
https://www.acmicpc.net/problem/15684
15684번: 사다리 조작
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선
www.acmicpc.net
알고리즘 유형: 백트래킹 + dfs
풀이: 만만히(?) 봤는데, 생각 보다 엄~~청 꼬여서 애먹었다.
처음에는 추가된 가로선의 배열을 깊은복사로 일일히 복사해주었고, 시간 초과가 발생했다..
그 뒤 방향을 잘못잡아 연달아 실수를 했고, 결국에 백트래킹 + dfs로 문제를 풀었다.
백트래킹 기법을 사용해 추가된 가로선의 배열을 true -> false로 복구 해주어 간단히 풀 수 있었다.
가로선 추가가 max 4개 이니 백트래킹과 dfs로 접근이 가능했던 것이다.
다음은 상세한 주석 + 코드이다.
# https://www.acmicpc.net/problem/15684
#
import sys
input = sys.stdin.readline
n,m,h = map(int, input().split())
answer = -1
graph = [[False] * (n+1) for _ in range(h+1)]
# 사다리 타기
# 1번 세로부터 시작
def go(graph):
for i in range (1,n+1):
# 현재 세로선
curLine = i
# 현재 점선 -> 초기화 1
curDotLine = 1
while curDotLine <= h:
# 사다리가 오른쪽 으로
if graph[curDotLine][curLine]:
curLine +=1
# 사다리가 왼쪽으로
elif graph[curDotLine][curLine-1]:
curLine -=1
curDotLine +=1
# 하나라도 세로선이 종착선과 다르면 return False
if curLine != i:
return False
# 모두 통과 -> return True
return True
# 가로선 추가에 대한 dfs
def dfs(x, y, cnt):
# 더이상 추가될 가로선이 없다 -> 사다리타기 go
if cnt == 0:
return go(graph)
for i in range(x, h+1):
for j in range(y,n+1):
# 가로선 추가가 가능 and "연달아 있는 가로선"이 없음.
if graph[i][j] == False and j <n and graph[i][j-1] == False and graph[i][j+1] == False:
graph[i][j] = True
# 가능 -> return True
if dfs(i,j,cnt-1):
return True
graph[i][j] = False
y = 0
for _ in range(m):
a,b = map(int, input().split())
graph[a][b] = True
# 가로선을 0개 부터 3개 까지 추가한다.
for i in range(4):
# 이전 가로선 추가로 해결이 안됨 -> 새 dfs
if(answer == -1):
if dfs(1, 1, i):
answer = i
break
print(answer)
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- typescript gsls
- vue ref
- react three fiber
- ts glsl
- vue
- react 3d
- Vue.js
- react fiber 3d
- react 3d animation
- react 3d text
- webpack glsl
- vue reactive
- react three fiber leva
- vue react
- 394 decode string
- 394. decode string javascript
- 394. decode string js
- next.js import glsl
- react 3d 에니메이션
- react ref reative
- attempted import error: bvh_struct_definitions' is not exported from './gpu/bvhshaderglsl.js' (imported as 'bvhshaderglsl').
- react vue
- react glsl
- [leetcode] 394. decode string
- eslint
- vue3
- leva
- react leva
- [leetcode] 394. decode string js
- three.js leva
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
글 보관함