문제 링크입니다: https://www.acmicpc.net/problem/17070
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이
www.acmicpc.net
파이프가 차지하는 두 칸 중 끝 칸만을 확인하면 쉽게 풀 수 있는 브루트포스 문제였습니다.
알고리즘은 상당히 간단한데 불가능한 경우를 가지치기 하면서 재귀함수를 호출하면 되는 문제였습니다.
가지치기하는 조건은 아래와 같이 세가지입니다.
1. 가로 -> 세로, 세로 -> 가로로 바로 회전할 수 없기 때문에 이 조건을 확인해줘야합니다.
2. 파이프의 끝이 범위를 벗어나거나 벽 위에 있을 경우 가지치기를 해줘야합니다.
3. 마지막으로 파이프의 방향이 대각선인 경우 가로와 세로인 경우와 다르게 확인해야할 벽이 두 군데 더 있습니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 17294번 귀여운 수~ε٩(๑> ₃ <)۶з (2) | 2019.08.04 |
|---|---|
| 백준 17069번 파이프 옮기기 2 (0) | 2019.08.04 |
| 백준 3197번 백조의 호수 (7) | 2019.08.01 |
| 백준 9376번 탈옥 (6) | 2019.07.31 |
| 백준 1015번 수열 정렬 (2) | 2019.07.30 |