알고리즘/백준저지
백준저지 2589번 보물섬 (Java)
출처: https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 접근 방법 변수 max : 답이 될 최댓값 cntL : 입력받을 때 센 L의 개수. L이 1이라면 답은 무조건 1이다. 메서드 int getCount(int x, int y, char[][] map) : 현재 위치 x,y와 입력 받은 map[][]으로 BFS를 수행하여 답이 될 이동횟수를 리턴시킨다. 코드 0. 입력을 받는다. 입력 받을 때 L 개수를 세서 cntL에 저장한다. 1. 지도 위 ..
백준저지 4179번 불!
출처: https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 접근 방법 1. 지훈의 위치를 저장할 큐, 불의 위치를 저장할 큐, 지훈과 불의 이동을 동시에 저장할 2차원 boolean 배열을 준비한다. 입력 받을 때, 지훈과 불의 위치를 각각 큐에 넣으면서 방문했다고 표시한다. 지훈의 위치는 '.'으로 바꾼다. 2. 입력받을 때부터 지훈이 벽에 붙어있다면 1을 출력하고 끝낸다. 3. 그 외의 경우, 지훈의 큐가 빌 때까지 또는 지훈이 ..
백준저지 17142번 연구소 3 (Java)
출처: https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 접근 방법 1. 연구소의 상태를 입력받으면서 바이러스의 위치를 리스트에 담는다. 2. 바이러스의 리스트 크기와 주어진 M을 통해 조합으로 M개의 바이러스를 구한다. 이때, 브루트포스 알고리즘으로 모든 경우를 생각한다. 3. BFS로 선택된 바이러스를 큐에 모두 담고 퍼뜨리기를 시작한다. 3-1. 매번 큐의 사이즈를 구해 사이즈만큼 for문을 반복한다. 그 안에서 4방 탐색을 진행한다. 3-2-1. ..
백준저지 1747번 소수&팰린드롬
출처: https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 접근 방법 숫자를 입력 받고 2부터 시작해서 반복문을 사용해서 구현한 에라토스테네스의 해를 통해 소수인지 확인한다. 소수가 맞다면 주어진 수보다 큰 경우(https://www.acmicpc.net/board/view/12646)에 팰린드롬인지 확인한다. int형 배열을 1003002 크기만큼 만드는데, 이유는 N의 최댓값인 1000000일 때 최대로 나..
백준저지 14442번 벽 부수고 이동하기 2 (Java)
출처: https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 접근 방법 백준저지의 벽 부수고 이동하기(https://www.acmicpc.net/problem/2206) 문제에서 벽의 개수만 추가된 문제다. 그래서 해당 문제의 코드(https://anott.tistory.com/54)와 거의 동일하다. 이전 문제에서는 부순 벽의 개수가 0개일 때만 부수고 이동하게 했다면, 이번에는 K개 이하일 때만 부수고 이동하게..
백준저지 2206번 벽 부수고 이동하기 (Java)
출처: https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 접근 방법 시작점부터 BFS로 4방 탐색을 진행한다. boolean 타입의 3차원 배열을 만들어서 벽을 부쉈는지 여부를 체크한다. 이동할 수 있는 곳(0)은 그냥 이동하고, 벽(1)을 만나면 현재 벽을 부순 상태인지 확인해서 그렇지 않은 경우만 이동한다. 이때, 벽을 아직 안 부순 현 상태를 true로 체크하고, 벽을 부순 자리를 큐에 넣는다. 생각 벽을 부술 때 ..
백준저지 1755번 숫자놀이
출처: https://www.acmicpc.net/problem/1755 1755번: 숫자놀이 79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 www.acmicpc.net 생각 한자리 수인 경우는 띄어쓰기 없이 하나의 단어만 출력하는 것을 몰라서 틀렸다. Comparator 사용하는 것이 아직 안 익숙해서 무식하게 정렬하고 해시에서 찾는 방법으로 구현했다. 입력이 99까지라서 시간 초과는 나지 않았다. 코드 import java.io.BufferedReader; import java.io.BufferedW..
백준저지 14502번 연구소
출처: https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근 방법 입력을 받을 때 빈칸의 위치를 리스트에, 바이러스의 위치를 큐에 담는다. 빈칸 위치들 중 3개를 조합으로 뽑아내서 벽을 세운다. 그리고 그때마다 bfs로 바이러스를 퍼뜨리고 안전영역의 수를 구한다. 이렇게 하기 위해서 맵과 큐는 매번 복사해서 사용한다. 그렇게 구한 안전영역들의 최소값이 답이 된다. 생각 조합 + BFS (토마토(https://www.acmicpc.net/problem/757..
백준저지 2667번 단지번호붙이기
출처: https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 제출 날짜: 2021년 9월 20일 월요일 접근 방법 입력을 받을 때 1이라면 -1로 바꿔 map에 저장했다. 그리고 단지 번호를 1부터 차례로 입력을 받았다. 단지 번호 붙이는 건 dfs를 사용했다. 생각 연결된 부분에 숫자를 붙이는 문제인데, 백준저지 다리 만들기 2(https://www.acmicpc.net/problem/17472)를 풀 때 사용해야했던 방법이다. 문제를 풀 때 시간이..
백준저지 1463번 1로 만들기
출처: https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 제출 날짜: 2021년 9월 15일 수요일 생각 문제 풀이 아이디어(https://www.acmicpc.net/board/view/61592)와 심화 테스트케이스 예시(https://www.acmicpc.net/board/view/63158)의 도움을 받아 문제를 풀 수 있었다. 코드 // 출처: 백준저지 1463번 1로 만들기 https://www.acmicpc.net/problem/1463 import java.io.BufferedReader; import java.io.BufferedWriter; ..