java

[JAVA] 백준 1194 : 달이 차오른다, 가자.

문제 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 해결방법 방문 체크가 중요한 문제이다. 열쇠가 a ~ f 가 존재하고 각 열쇠에 해당되는 문이 A ~ F가 존재한다. 방문 체크를 열쇠를 아예 들고 있지 않을 때, a만 들고 있을 때, a와 b를 들고 있을 때 등으로 나누어서 체크를 해주어야 한다. 그렇게 하면 총 6개 열쇠를 모두 방문 체크를 해주어야 되기 때문에 좌표값 + 6 해서 8차원 배열을 사용해야 한다. 그래서 비트 마스크를 사용한다. 비트마스크를 사용하면 아예 사..

[JAVA] 백준 2636 : 치즈

문제 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 해결 방법 조금 생각할 것이 있는 구현 문제이다. 필자는 다음과 같은 순서로 문제를 해결했는데, 1. 배열의 (0, 0) 부터 빈 공간인 0을 탐색, 만약 0의 상하좌우에 치즈 즉, 1이 있다면 Queue에 넣음. 모든 공간을 다 탐색하면 Queue에 넣어진 치즈들이 한 시간 후 녹을 치즈들이 됨. 재귀를 통해서 모든 치즈들이 없어질 때까지 탐색을 계속함. 2. Queue에서 치즈를 꺼내면서 빈공간으로 바꿔주면서 상하좌우에 있는 치즈를 찾음. 만약 치즈가 있다면 다..

[JAVA] 백준 16567 : 바이너리 왕국

문제 16567번: 바이너리 왕국 첫째 줄에 바이너리 길의 칸의 개수 N, 시련의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에 N개의 현재 바이너리 길의 상태가 주어진다. 그다음 M개의 줄에 걸쳐서 시련이 주어진다. 이때 0 www.acmicpc.net 해결 방법 간단한 문제인데 조건을 빼먹어서 오래 걸렸습니다. 처음에 바닥의 상태가 주어질 때 연속으로 더러운지 아닌지 확인하면서 카운트를 증가시켜줘야합니다. 다음에 M개의 명령이 주어질 때 0의 경우일 때는 카운트를 출력하고 1의 경우일 때는 총 4가지를 생각해야합니다. 1. index가 0일 때 자신의 다음 칸이 깨끗하다면 카운트를 1증가 2. index가 마지막일 때 자신의 이전 칸이 깨끗하다면 카운트를 1증가 3. 그 외..

[JAVA] 백준 1637 : 날카로운 눈

문제 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 해결방법 개인적으로 이해하는데에 많은 시간을 소모해서 다음에 이와 같은 문제를 봤을 때 이해하는 속도를 높히고자 글을 작성해둔다. 이 문제는 정수더미에 수 많은 숫자들이 들어있고, 그 중에서 하나의 숫자만 홀수개 존재하는데 그래서 정수더미에 있는 수 중 홀수개 존재하는 숫자가 무엇인지 또 몇 개 들어있는지를 출력하는 문제이다. 예제 1의 입력을 보면 1 10 1 과 같이 3개의 숫자가 주어지는데 의미는 ..

[JAVA] 백준 13913 : 숨바꼭질 4

문제 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 해결 방법 오랜만에 알고리즘 해설을 준비했는데, 그리 어렵지 않은 문제이다. 어려운 문제는 어떻게 풀어야 할지 아직 감이 잘 안 잡혀서, 문제를 풀더라도 설명을 할 정도로 이해를 하지 못해 가져오지 못했다. 이 문제는 수빈이가 동생을 찾는 숨바꼭질 문제인데, 수빈이는 현재 위치에서 +1, -1 또는 x2 만큼 움직일 수 있고 움직일 때마다 1초씩 소모된다. 즉, 모든 경우의 수를 전부 확인하며 목표지점에 도달하는 시간을 체크..