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의 존재 여부를 체크해주면서 실행하면 된다.


[소스코드]


'ALGORITHM > BOJ' 카테고리의 다른 글

[BOJ] 15927번 회문은 회문아니야!! (C++)  (0) 2021.12.27
[BOJ] 7490번 0 만들기 (C++)  (0) 2021.12.21
[BOJ] 1477번 휴게소 세우기 (C++)  (0) 2021.12.21
[BOJ] 2776번 암기왕 (C++)  (0) 2021.12.20
[BOJ] 2343번 기타 레슨 (C++)  (0) 2021.12.20