(JAVA) 백준 15683번 : 감시

https://www.acmicpc.net/problem/15683

15683번: 감시

 

 

삼성 역량 SW 테스트 기출 문제 중 하나이다.

 

브루트 포스 + 시뮬레이션으로

 

문제는 길어보이지만

 

조건들을 유심히 생각해서 알고리즘을 작성하면 된다.

 

 

핵심은

 

1. 각 CCTV 종류 별 가능한 방향 개수 파악하기

*** 1: 4개,   2: 2개,   3: 4개,   4: 4개,   5: 1개.

 

 

2. 벽과 CCTV가 존재하는 구역은 사각지대가 아니므로 사각지대 계산 시 주의!

*** 나는 전체 사각지대가 가능한 구역의 개수 - 사각지대가 아닌 구역의 개수 를 통해 사각지대의 개수를 파악함.

 

 

3. 벽에 닿으면 감시를 종료하지만 CCTV에 닿게 되더라도 감시는 계속 진행한다.

 

 

 

바로 매커니즘으로 넘어가겠다.

 

매커니즘

---

 

1. Input 값을 읽으면서 map 그리기.

이 때, 입력 값이 1 ~ 5 인 경우에는 CCTV이므로 이때의 x, y, 입력 값이 담긴 CCTV 클래스 객체를 만들고,

별도의 list에 저장한다.

 

 

빨간색 글씨가 경우의 수...

2. CCTV도 type 별로 감시하는 방향의 경우의 수가 존재하므로

이러한 경우의 수를 각각 담아서 체크하기 위한 백트래킹 함수 실행

 

 

3. 2를 진행하기 위해 백트래킹 함수 내부에서 type별로 for문 작성하여 경우에 따른 방향 담기

 

 

4. 백트래킹 경우 하나하나 씩 따져가며 체크하기

   -> Map과 bool 2차원 배열로 체크할 수 있다.

   -> direction에 따라 x, y 좌표 값을 증가시키며 진행

   ** direction : 0(위), 1(오), 2(아래), 3(왼)

   ** x, y 좌표가 Map을 벗어날 수 있다는 것에 유의!

       -> Map 내 x,y 원소 값이 6인 경우 : 반복문 종료.

       -> Map 내 x,y 원소 값이 0이면서 bool 2차원 배열 내 x,y 원소 값이 False인 경우 : 감시한 영역 count ++, True로 변경. x, y 값 변경 후 반복

       -> 그 외 : x, y 값 변경 후 반복

 

 

5. 전체 감시 가능 영역 개수 - 감시한 영역 개수 가 최소인 값 출력

 

 

 

 

 

맨 밑에 소스코드 첨부했습니다.

감사합니다.

 

 

*** 백준 질문에 올라온 여러 테스트케이스가 담긴 게시글 주소를 첨부합니다.

https://www.acmicpc.net/board/view/48178

글 읽기 - 15683번 예제 데이터 및 주의할 점을 모아봤습니다.

 

소스코드

---