Joonas' Note

BOJ 15683 - 감시 본문

알고리즘/문제 풀이

BOJ 15683 - 감시

joonas 2018.05.17 17:58

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

문제

모든 조합을 살피고 시뮬레이션을 할 수 있어야 하는 문제.

CCTV가 보고 있는 방향을 하나씩 선택하면서, 모든 방향이 결정됐을 때 시뮬레이션 후 사각 지대의 개수를 구한다.
모든 조합을 살피다가 사각 지대의 개수가 최소가 되는 조합에서 정답을 출력하면 된다.

CCTV의 방향을 처리하는 시뮬레이션이 벽에서 막힌다거나 지도 밖으로 넘어가는 것 외에도 은근히 신경쓰이는 게 많다.
오목이나 틱택토류의 코드를 작성한 경험이 있다면 수월할 듯

상세한 부분을 제외하면 개략적인 구조는 이렇다.

여러 방향을 한번에 담아 처리하기 위해 비트로 각 방향을 표현했다. 비트가 겹치는 것을 확인하는 건 비트 AND연산으로 쉽게 구현할 수 있다. 예를 들어, 0010(2) AND 0111(2) 의 결과는 0010(2) 이므로 겹치는 부분이 있다. 0100(2) AND 0001(2) 는 0000(2)라서 겹치지 않는다.

전체 코드

코드보기

'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 13701 - 중복 제거  (0) 2018.05.18
BOJ 15719 - 중복된 숫자  (0) 2018.05.18
BOJ 15683 - 감시  (0) 2018.05.17
BOJ 1525 - 퍼즐  (0) 2018.05.08
BOJ 2225 - 합분해  (0) 2018.04.24
BOJ 3075 - Astromeeting  (0) 2018.04.18
0 Comments
댓글쓰기 폼