Algorithm

[백준] 16947. 서울 지하철 2호선 (Java)

문제 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 알고리즘 그래프, 깊이우선탐색(DFS), 너비우선탐색(BFS) 풀이 DFS를 통해 사이클(순환선)을 찾아 표시하고, BFS를 통해 사이클이 아닌 노드에서 사이클인 노드까지 최소 거리를 구해 문제를 해결하였다. 사이클 찾기 ( DFS ) 모든 역은 연결되어있으므로 임의의 한 역에서 출발하여 DFS로 모든 간선을 탐색한다. 이때 이미 방문한 노드를 다시 방문한다면 사이클이 있는 것이므로 해당 노드까지 다시 되돌아가며 그 사이 역들을 모..

[백준] 16929. Two Dots (Java)

문제 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 알고리즘 그래프, 깊이우선탐색(DFS) 풀이 그래프에 같은 색으로 이루어진 사이클이 있는지 찾는 문제이다. 사이클은 점의 개수가 4보다 크거나 같아야하며 마지막 점이 출발 점과 같은 색이어야한다. 따라서 그래프의 각 점을 출발점으로 하여 DFS를 진행해 사이클이 발생하는 점이 있는지 확인한다. DFS를 위한 재귀 함수의 매개변수로 시작점의 좌표, 현재 점의 좌표, 지나온 점의 개수를 전달한다. 함수의 흐름은 다음과 같다. 현재 점과 인접한 점 (ny..

[백준] 16948. 데스 나이트 (Java)

문제 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 알고리즘 그래프, 너비우선탐색(BFS) 풀이 기존 사방으로 탐색했던 BFS 과정을 문제에서 주어진 6 방향으로 바꾸기만 하면 되는 문제이다. 좌표와 이동 횟수를 큐에 삽입해 6 방향으로 탐색하며 (r2,c2)에 도달했다면 그때의 이동 횟수를 출력하고 도달하지 못하고 BFS 가 종료되었다면 -1 을 출력한다. * 큐에 삽입하므로 최소 이동 횟수가 적은 상태부터 탐색한다. 따라서 도달..

[백준] 4574. 스도미노쿠 (Java)

문제 4574번: 스도미노쿠 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 www.acmicpc.net 알고리즘 브루트포스, 구현, 백트래킹 풀이 문제 설명에 오해의 소지가 있는 것 같다. 우선 36개의 도미노 타일은 종류 별로 모두 한 번씩 사용해야한다. (1 + 2) ~ (8 + 9) 까지의 개수가 36개이다. 또 문제에 "도미노 타일은 회전 시킬 수 있다." 고 주어져있는데 입력으로 주어지는 이미 채워진 도미노 쌍은 고정된 것으로 회전하지 않는다. 따라서 각 그리드에 대해 인접한 그리드의 값도 같이 정해주는 스도쿠 문제인 셈이다. 도미노..

[백준] 2580. 스도쿠 (Java)

문제 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 알고리즘 브루트포스, 백트래킹 풀이 빈 칸에 1부터 9까지 모든 수를 넣어보며 가능한 경우 다음 빈 칸으로 넘어가는 식으로 모든 빈 칸을 채웠을 때 결과를 출력한다. 1. 각 빈 칸의 좌표를 리스트에 저장한다. 2. 0번째 빈 칸부터 1~9까지 유효한 수를 찾는다. 3. 유효하다면 빈 칸을 그 수로 채우고, 다음 빈 칸으로 넘어간다. 4. 리스트의 마지막 빈 칸까지 채웠다면 결과를 출력한다. 유효성 확인 (y, x) 좌표에 num을 삽입할 수 있는지 확인한..

[백준] 16197. 두 동전 (Java)

문제 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 알고리즘 깊이우선탐색(DFS), 백트래킹 풀이 깊이우선탐색을 통해 상하좌우 네 방향으로 동전을 이동시키며 모든 경우를 탐색해 최소 횟수를 찾는다. 아이디어는 다음과 같다. 1. 동전의 위치를 보드 배열에 'o' 로 표시하는게 아니라 (y1,x1) (y2,x2) 좌표로 관리한다. 보드 배열을 수정하지 않음으로써 구현을 편하게 할 수 있다. 2. [N+2][M+2] 크기의 배열을 선언하여 테두리는 초기화된 0 그대로 두고, 그 안쪽 [N][M] 크기만 입력으로..

[백준] 16198. 에너지 모으기 (Java)

문제 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 알고리즘 브루트포스 알고리즘 풀이 x번째 에너지 구슬을 제외하는데 첫 번째와 마지막 에너지 구슬은 고를 수 없으므로 총 N-2 개의 구슬을 제거해야한다. N이 최대 10이므로 N-2 는 최대 8이고, 즉 최대 8개의 구슬 중 제거할 구슬의 순서를 정하는 일이므로 경우의 수는 8! = 약 40,000 개이다. 따라서 전체 경우의 수를 탐색해 에너지 양의 최댓값을 구한다. 에너지 구슬을 고르면 그 구슬은 제거되므로 이미 제거된 구슬인지 확인하기 위한 boo..

[백준] 15658. 연산자 끼워넣기 (2) (Java)

문제 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 알고리즘 브루트포스 알고리즘 풀이 N개의 수가 주어지므로 연산자의 수는 N-1개가 된다. N이 최대 11이므로 N-1은 최대 10이고, 연산자의 종류는 4가지이므로 만들 수 있는 경우의 수는 4^10 = 2^10 * 2^10 로 약 100만 가지이다. 따라서 모든 경우의 수를 탐색하며 최대, 최소값을 갱신한다. 연산자마다 개수가 정해져있기 때문에 이를 배열에 저장하고, 해당 연산자의 남은 개수가 1보..

[백준] 14225. 부분수열의 합 (Java)

문제 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 알고리즘 브루트포스 알고리즘 풀이 수열의 크기 N이 최대 20이고, 부분 수열이므로 각 숫자가 선택되거나, 선택되지 않는 2가지 경우로 나눈 부분집합으로 만들 수 있는 경우의 수는 2^20 = 1024 * 1024 = 약 100만개이다. 따라서 모든 부분 수열의 합을 찾고, 1부터 증가시키며 나오지 않은 가장 작은 자연수를 출력한다. S의 원소가 최대 100,000이고 크기 N이 최대 20이..

[백준] 20055. 컨베이어 벨트 위의 로봇 (Java)

문제 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 알고리즘 구현, 시뮬레이션 풀이 각 칸의 내구도를 저장할 [2][N + 1] 크기의 2차원 배열 A와 각 칸에 로봇이 있는지 저장할 [N + 1] 크기의 1차원 배열 R을 만든다. R이 1차원인 이유는 로봇에 1번 칸에서 시작해 N번 칸에 도착하면 "내린다", 즉 삭제되기 때문에 N+1 ~ 2N 칸에는 로봇에 있을 수 없기 때문이다. 반복 횟수가 K가 될 때까지 다음 과정을 반복하며 내구도가 0인 칸의 수를 센다. 1. 벨트 회전 2. ..