[백준/JAVA] 1261번: 알고스팟
문제 보러가기 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net [문제 풀이] 다익스트라를 사용하여 풀었는데, 사실 풀고나서도 긴가민가하다. 좌표 이동을 (x+1, y), (x-1, y), (x, y+1), (x, y-1)로 하면서 동시에 좌표 이동했을 때에 뚫게 되는 벽의 수를 기존의 다익스트라 배열 값과 비교하여 좌표 이동했을 때가 벽의 수가 더 적다면 배열을 갱신을 하고 이동된 좌표를 큐에 넣는다. 큐에서 좌표를 꺼내 다시 좌표이동을 하고 비교를 하였다. 다익스트라 배열에는 해당 좌표..
[백준/JAVA] 1285번: 동전 뒤집기
문제 보러가기 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net [문제 풀이] 이 문제의 태그에 비트마스킹이 있는 이유는 모든 행의 조합을 따져서 동전을 뒤집어봐야한다. 예제를 보면 N = 3일 때 1행, 2행, 3행이 있다. 이때 {1행}, {2행}, {3행}, {1, 2행}, {1, 3행}, {2, 3행}, {1, 2, 3행} 등의 조합을 고려해서 경우의 수를 따져야하기 때문에 비트마스킹이 필요하다. 물론, 아무 행도 고르지않는 경우의 수도 따져야 한다. N에 따라 조합이 몇 개인가 따지자면, 2 ^ N..