[C++] 백준 15683번 감시

15683번: 감시

문제가 길어서 링크로 대체하겠다.

구현, 시뮬레이션, 브루트 포스 문제.

노가다해서 풀었는데, 사실 마땅한 좋은 방법이 딱히 떠오르지가 않았다.

코드 길이가 너무 길어서 비효율적이라고 생각하지만, 시간은 빠르게 나왔다.

 

문제풀이

CCTV가 1번부터 5번까지 있다. 각 번호마다 감시하는 방향이 존재하는데, CCTV는 90도 회전이 가능하다.

이 때, CCTV들의 방향을 설정해서 사각지대가 최소가 될 때 몇 개가 되는지 구하는 문제이다.

 

1번 CCTV가 가능한 모든 경우는 (↑ / → / ↓ / ←) 총 네 가지이다.

2번 CCTV가 가능한 모든 경우는 (←→ / ↑↓) 총 두 가지이다.

3번 CCTV가 가능한 모든 경우는 (ㄴ / ↓→ / ←↓ / ←↑) 총 네 가지이다.

4번 CCTV가 가능한 모든 경우는 ( ㅗ / ㅏ / ㅜ / ㅓ ) 총 네가지이다.

5번 CCTV는 상, 하, 좌, 우 모두 고려하는 한 가지의 경우가 있다.

 

각 CCTV마다 모든 경우를 다 고려해줘서 사각지대가 최소가 될 때를 찾아서 출력하면된다.

이 때 CCTV가 감시하는 방향에

• 벽이 있다면, 거기서 멈춘다. CCTV는 벽 뒤는 감시할 수 없다.
• 다른 CCTV가 있다면, 해당 CCTV를 통과해서 감시한다.

 

위 조건들을 고려해서 구현해주면 된다.

 

사용한 STL과 변수

• height, width : 높이와 너비
• office : 사무실의 정보
• ans : 정답.
• cctvVec : CCTV의 번호와 좌표를 담아놓는 벡터. 일일이 나중에 CCTV좌표를 찾을 필요가 없다.
• direction[4] : 상, 우, 하, 좌를 살펴보는 더하는 방향을 담아놓는 배열

 

한 방향에 있는 빈칸들을 감시하는 곳으로 바꿔주는 메서드

cctvSetChecked 메서드는 시작 칸부터 방향대로 움직이면서 차례대로 빈 칸일 경우 감시하는 칸으로 바꿔준다.

이 때 감시하는 칸을 9로 만들었는데, 다른 CCTV도 같은 곳을 감시한다면 나중에 0으로 바꿀 때 잘못된 결과가 나올 수 있으므로 9인 칸은 +1을 해주는 형식으로 만들었다. 그리고 벽을 만나거나, 잘못된 범위라면 return한다.

 

cctvSetUnChecked 메서드는 setChecked메서드와 마찬가지이지만, 반대라고 생각하면 된다. 감시를 푸는 메서드이다.

 

위 메서드는 한 방향만을 고려하므로, 각 CCTV마다 방향을 고려해줘서 만들어주면 된다.

메인함수

메인 메서드에서는 높이와 너비를 입력받는다. 그리고 사무실 각 칸의 정보를 입력받는데,

만일 1<= input <= 5, 즉 CCTV라면 CCTV벡터에 정보를 담아놓는다.

그리고 ans에 최초에 빈 칸들을 초기화시켜놓기위해서 0의 수만큼 초기화해놓는다.

 

그리고 solve라는 탐색 메서드를 실행시켜서 탐색해준다.

 

탐색 메서드

만일 idx, 내가 현재 탐색하는 번째 수가 CCTV벡터의 사이즈보다 크거나 같다면, 즉 더 고려할 CCTV가 없다면 현재 사무실에서 빈 칸들을 찾아서 ans와 비교한 후 더 작은 값을 ans에 더해준다.

 

아직 더 탐색해볼 CCTV가 남아있다면 CCTV 번호에 따라 탐색을 시작한다.

CCTV 번호에 따라 방향을 고려해보며 백트래킹과 유사한 형식으로 구현해보았다.

이 방향을 해보고 저 방향을 해보고 다 고려해 보는것이다.

 

 

위처럼 모든 것을 다 고려해 준다면 문제를 맞출 수 있다.

문제는 쉽게 맞출 수 있었는데, 코드가 너무 길게나온 것 같다.

좀 더 효율적으로 코드 길이를 줄일 수 있는 방법이 없을지 고민해봐야겠다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.