ALGORITHM/BOJ
[BOJ] 17070번 파이프 옮기기 1 (C++)
yegyeom
2021. 12. 21. 12:02
문제 (https://www.acmicpc.net/problem/17070)
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
가능한 이동 방법은 아래와 같다.
1. 파이프가 가로 방향일 때
- 오른쪽 방향
- 오른쪽 아래 대각선 방향
2. 파이프가 세로 방향일 때
- 아래 방향
- 오른쪽 아래 대각선 방향
3. 파이프가 대각선 방향일 때
- 오른쪽 방향
- 아래 방향
- 오른쪽 아래 대각선 방향
파이프의 오른쪽 끝 위치(x, y), 현재 파이프의 방향(가로/세로/대각선)(dir)과 함께 dfs를 실행하면 된다. 나는 dir을 0: 가로, 1: 세로, 2: 대각선으로 설정했고 3가지 이동방향도 가로-세로-대각선 순서로 저장해두었다.
- dir이 0이고 이동방향이 1인 경우는 (파이프: 가로, 이동: 세로) 불가능하므로 제외
- dir이 1이고 이동방향이 0인 경우는 (파이프: 세로, 이동: 가로) 불가능하므로 제외
- 나머지 경우는 파이프를 이동했을 때 1의 존재 여부를 체크해주면서 실행하면 된다.
[소스코드]
