전체 글
BOJ 2457 공주님의 정원 [Java]
BOJ 2457 공주님의 정원 1. 문제 링크 https://www.acmicpc.net/problem/2457 2. 문제 해설 그리디 알고리즘을 이용하여 푸는 문제이다. 백준 문제 중 1931번 회의실 배정과 비슷한 결을 가진 문제이다. 1931번을 풀어보지 않았다면 먼저 풀어보도록 하자. https://www.acmicpc.net/problem/1931 다시 문제로 돌아와서, 일단 그리디를 이용해서 풀면 될 것 같다는 생각은 들었지만 그리디를 이용하려면 검증이 필요하다. 매번 최선의 선택을 한 것이 전체적으로 봤을 때도 최선의 답이라는 것을 검증해야한다. 그 전에 일단 내가 어떻게 문제를 그리디적으로 접근했는지 살펴보자. 1. 3월 1일을 기준일로 잡는다. 2. 기준일보다 일찍 피는 꽃들 중에서 가장..
BOJ 9663 N-Queen [Java]
BOJ 9663 N-Queen 1. 문제 링크 https://www.acmicpc.net/problem/9663 2. 문제 해설 퀸이 체스판에서 서로 공격할 수 없으려면 3가지 조건을 다 만족해야한다. 같은 행, 같은 열, 대각선 상에 퀸이 존재하면 안된다. 여기서 우리가 퀸을 한 행에는 한개씩만 두기로 해보자. 그렇다면 퀸이 같은 행에 존재하는 경우는 없으므로 조건 중에 1가지는 생각하지 않아도 된다. 1차원 배열을 이용하여서 퀸의 위치를 표현했다. queen[i] = j 라고 하면, i번째 행의 퀸은 j열에 존재한다라는 의미이다. 퀸을 놓는 것은 백트래킹 과정을 이용하여 간단하게 해결가능하다. 23~37줄의 solve 메서드를 살펴보자. solve 메서드의 매개변수는 r로 현재 행을 의미한다. 그러므..
BOJ 11559 Puyo Puyo [Java]
BOJ 11559 Puyo Puyo 1. 문제 링크 https://www.acmicpc.net/problem/11559 2. 문제 해설 문제에서 요구하는 구현해야할 기능을 크게 3가지로 나누어보겠다. 1. 터트릴 뿌요를 파악하기 - bfs 메서드 : 같은 색 뿌요가 4개 이상 연속되는 경우를 찾아야한다. bfs, dfs를 이용하면 되겠다는 생각이 들었는데 dfs를 이용하면 ㅗ, ㅜ 같은 모양으로 연속되있는 경우를 처리하기가 까다롭기에 bfs를 이용하기로 결정하였다. 같은 색 뿌요가 연속되는 경우 list에 담아 list의 크기가 4 이상이면 터트릴 수 있고 아닌 경우는 터트릴 수 없는 방식으로 처리하고자 하였다. 2. 뿌요를 터트리기 - explode 메서드 : list에 담겨 있는 뿌요를 빈 칸으로 만..
BOJ 15686 치킨 배달 [Java]
BOJ 15686 치킨 배달 1. 문제 링크 https://www.acmicpc.net/problem/15686 2. 문제 해설 백트래킹을 이용하는 문제이다. 백트래킹의 대표적인 문제 n과 m 시리즈를 업그레이드한 문제라고 생각한다. 문제를 읽어보면 구현해야할 것은 크게 2가지이다. 1. 치킨 집을 m개 고르기 2. 치킨 집을 m개 고른 각 경우의 수마다 도시의 치킨 거리 구하기 이 2가지 기능을 이용해서 어떻게 전체적인 흐름이 돌아가는지 한번 설명해보겠다. 일단 치킨 집과 집의 위치를 arraylist에 담아준다. 그 후, 백트래킹을 이용하면 치킨 집을 m개 고르는 모든 경우의 수를 구할 수 있다. 여기서 m개를 고른 각 경우의 수마다 도시의 치킨 거리를 구해주고 그 중 최솟값이 정답이 된다. 3. 코..
BOJ 1260 DFS와 BFS [Java]
BOJ 1260 DFS와 BFS 1. 문제 링크 https://www.acmicpc.net/problem/1260 2. 문제 해설 그래프에서의 dfs와 bfs를 할 수 있는지를 묻는 문제이다. 인접 리스트를 이용하여 그래프를 표현해주고 dfs와 bfs를 돌려주면 된다. 주의할 점 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 점이다. : 인접 리스트에서 각 정점의 원소들을 오름차순으로 정렬해주면 쉽게 해결할 수 있다. 2. dfs를 비재귀적인 방식으로 풀 경우 재귀적인 dfs와 방문 순서가 다를 수 있다. : 나는 dfs를 재귀적인 방식으로 풀었지만, 재귀적인 방식이 아닌 stack을 이용해서 풀 경우 방문 처리를 제대로 해주지않으면 재귀적인 방식과 방문 순서가 ..