저번 문제와 마찬가지로 삼성 A형 기출문제, 역시 완전탐색 기반이긴 하지만 다른문제들보다 좀 더 쉬웠던것 같다.
https://www.acmicpc.net/problem/17070
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이
www.acmicpc.net
먼저 파이프가 한 번에 90도로 꺾일 수 없다는 조건이 있기 떄문에 전에 파이프가 어떻게 설치되어 있는지 알 수 있는
변수가 필요하다. 나는 가로, 대각선, 세로 이런식으로 배열에 배치한 다음, 현재 파이프가 어떻게 설치되어 있는지 기준
앞뒤로 한 칸씩만 갈 수 있도록 하여, 90도로 꺾이는 파이프가 없도록 만들었다.
그리고 파이프를 설치할때 가로와 세로는 가는방향에만 벽이없다면 괜찮지만 대각선방향으로 갈때는 가는 방향말고도
위쪽과 왼쪽 방향에 벽이없어야 하기 때문에 한 번더 체크 해주어야 한다.
위 2가지 예외 사항만 없다면 단순한 dfs구현이므로 문제 자체는 쉬운편인듯 하다.
https://github.com/MingNine9999/algorithm/blob/master/Problems/boj17070.cpp
MingNine9999/algorithm
Contribute to MingNine9999/algorithm development by creating an account on GitHub.
github.com
+) DP로 풀면 더욱 빠르게 값이 나온다는 걸 생각하고 DP로 다시 풀어보았다.
https://mingnine9999.tistory.com/22
백준 17070. 파이프 옮기기 1_ver2 (DP)
전에 올렸던 파이프 옮기기 1 문제인데, 그 땐 범위가 작아서 단순 나이브하게 DFS로 탐색했는데, DP를 이용해서 풀면 훨씬 속도가 빠를 것 같아서 다시 풀어보았다. https://www.acmicpc.net/problem/17070 17070..
mingnine9999.tistory.com
'프로그래밍 > 알고리즘 문제 풀이' 카테고리의 다른 글
| 백준 17370. 육각형 우리 속의 개미 (0) | 2020.05.22 |
|---|---|
| 백준 17070. 파이프 옮기기 1_ver2 (DP) (0) | 2020.04.29 |
| 백준 17281. ⚾ (0) | 2020.04.27 |
| 백준 16637. 괄호 추가하기 (0) | 2020.04.27 |
| 백준 17471. 게리맨더링 (0) | 2020.04.23 |
