비트마스킹

[백준 1322] X와 K (C++)

1322번: X와 K 첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net X + Y = X | Y 위 식의 의미는 다음과 같다. 두 수를 2진수로 바꾸었을 때 x와 y가 가진 비트 '1'의 위치가 모두 서로 다르다는 뜻이다. 같은 말로 X의 비트가 0인 위치에만 1이 채워져 있는 수가 Y가 될 수 있는 수이다. 문제를 풀기 위해서는 위 아이디어를 다음과 같이 응용하면 된다. 7번째 Y 값을 찾고싶을 때 7은 2진수로 바꾸면 111 이다. X를 5로 가정하면 X는 ..000101 이라고 생각할 수 있다. 여기서 비트 1의 위치는 보지않고 0인 위치를 숫자가 들어갈 수 있는 위치라고 생각하자. 따라서 7이라는 숫자가 들어갈 수 있는 비..

[백준 1525] 퍼즐 (C++)

1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net BFS, 비트마스킹 3x3 크기의 퍼즐은 각 칸마다 0~8까지의 숫자가 들어간다는 것을 이용해서 하나의 숫자당 4개의 비트를 사용. long long 타입에서 총 36개의 비트를 사용해 3x3 퍼즐의 정보를 저장하도록 했다. 위 퍼즐에서 0의 위치는 3행 3열에 있다. 따라서 32번째 비트~35번째 비트 공간이 해당 칸을 저장하게된다. 그리고 특정 칸에 위치한 숫자를 알아내기 위한 mask로서 Checker배열을 설정했다. BFS를 수행하면서 매번 0의 위치를 찾아준다. 0의 위치를 찾았다면 0이 갈 수 있는 4방향을 모두 탐색해본다. 범..

[백준 2234] 성곽 (C++)

2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 비트마스킹, BFS [백준 16946] 벽 부수고 이동하기 4 (C++) 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 hyeo-noo.tistory.com 위 문제와 아주 비슷한 방법을 적용해서 풀었다. 차이점은 N과 M의 크기가 현재 문제에서는 50, 50이 최대라서 O(N^2 * M^2)이 가..

[백준 17182] 우주 탐사선 (C++)

17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍, 비트마스킹 [백준 13308] 주유소 (C++) 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리 hyeo-noo.tistory.com 얼마 전 위 문제를 풀면서 다익스트라와 dp를 함께 쓰는 방법에 익숙해진 덕분에 풀 수 있었다 모든 행성이 서로 이..

[백준 14939] 불 끄기 C++

14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 그리디 알고리즘 1. 문제해결 아이디어 전구의 가장 윗 라인에서 스위치를 누르는 모든 경우(2^10=1024)를 시도해 본다. 그리고 두 번째 라인을 부터는 현재 열의 바로 윗 행의 전구가 켜져있는지 꺼져있는지에 따라서 스위치를 누를지 말지가 결정된다. 만약 바로 윗 행의 전구가 켜져있는데 현재 열의 스위치를 누르지 않는다면 앞으로 윗 행의 전구를 끌 방법은 없기 때문이다.(방향 : 왼쪽 상단부터 오른쪽 하단) 이렇게 하면 1~9 행은 모든 전구가 꺼질..