Joonas' Note

Joonas' Note

BOJ 15683 - 감시 본문

알고리즘/문제 풀이

BOJ 15683 - 감시

2018. 5. 17. 17:58 joonas

    링크: 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 - 중복된 숫자  (2) 2018.05.18
    BOJ 1525 - 퍼즐  (0) 2018.05.08
    BOJ 2225 - 합분해  (0) 2018.04.24
    BOJ 3075 - Astromeeting  (0) 2018.04.18
    Comments