Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처치킨배달 골드 5 📖 문제 // 치킨 거리 = 집과 가장 까가운 치킨집 사이의 거리// 집 기준, 집은 치킨거리를 가짐// 도시의 치킨 거리 = 모든 집의 치킨 거리의 합// 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|// 0 빈칸 , 1 집 , 2 치킨 집// 집의 개수  치킨 집 중 M개를 골라야하기에 백트래킹이 필요하다. 중요한 것은 전체 치킨 집 수 중 M개를 뽑는 방법이다.  처음에 그냥 i = 0 으로 모든 치킨집을 순회하면서 조합을 만들어갔기에 시간초과로 실패했다.중요한 것은 m개의 치킨집을 효율적으로 뽑아서 치킨거리를 계산하는 것이다. 치킨집을 뽑을때 이전에 뽑았던 가게는 이미 뽑혔기에 굳이 또 방문할 필요없다. ..

🧫 문제 분석 ✔️ 출처숨바꼭질 3 골드 5 📖 문제 bfs는 가중치가 같으면 항상 최단거리이다. x - 1, x + 1, x * 2 로 x가 k가 될 때까지 이동한다.n >= k 일 시 (x - 1) 로만 k로 갈 수 있기에  이를 고려한다. 정답 : n - kn과 k 는 0 ~ 100,000 사이이다. x - 1, x + 1, x * 2 인 노드를 bfs로 x(수빈)이가 k(동생)을 찾을때까지 반복하여 탐색한다.   🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static class Node { int cur, cost; public Node(int next, int cost) { ..

🧫 문제 분석 ✔️ 출처암호 만들기 골드 5 📖 문제  조건최소 한개의 모음 && 두 개 이상의 자음 알파벳이 사전 순서대로 정렬   ex) ba 불가능, ab 가능  알파벳을 배열에 담고 오름차순 정렬한 다음 길이를 주고 각 자리수에 맞게 완전탐색을 해본다. 처음(0일때) a일 경우 a를 방문했다고 하고 나머지 c i t s w 에 대해서 또 DFS를 한다. 중요한 것은 이전 사전 순이기에 이전 알파벳보다 현재 알파벳이 커야한다.(순서로 따지자면 뒷 번호여야 한다.)따라서 이전 알파벳에 대한 인덱스를 매개변수로 넘긴다.   그리고 모음의 만들어야하는 암호의 길이 L - 모음의 개수 = 자음의 개수이다.    🔅 문제 풀이import java.io.BufferedReader;import java.i..

🧫 문제 분석 ✔️ 출처인구 이동 골드4 📖 문제 랜덤 문제를 돌리다가 나왔다. 그래프 탐색 냄새가 솔솔 난다. BFS를 사용하면 될것 같다.  1. 한 나라의 좌우 상하로 인접한 다른 나라와의 인구차를 M명이라 했을 때 L 해야한다.2. 조건을 만족한 나라들과는 연합을 하여 국경선을 하루 연다. 3. 인구가 이동하며 각 나라의 인구수는 (연합 인구수 / 연합한 나라 개수) 가 되며 소수점은 버린다. 4. 이동후 연합 해지 및 모든 국경선을 닫는다.5. 인구 이동이 없을때까지 반복한다.6. 인구 이동이 며칠동안 발생했는지가 문제이다.  내가 생각한 방법1. 우선 연합가능한 나라들을 찾고, 그 나라에 연합 번호를 매기며 각 인구수를 더해놓는다. 2. 연합은 1개 이상 생길 수 있다. 3. 만약 1번 연..

🧫 문제 분석 ✔️ 출처숨바꼭질 1697번 - 백준 📖 문제🔅 문제 풀이수빈이의 위치 x동생의 위치 k수빈이는 -1, +1, *2 로 이동할 수 있고 이는 1초를 사용한다.graph를 조건에 만족하는 최대 크기로 만들어서 각 위치에 따른 초를 적을 것이다.처음 수빈이가 있는 장소는 1로 초기화한다. 너비우선탐색으로 하되 문제에서 주어진 위치에 대한 조건식을 걸어주고 (0 이동하려는 곳에 이전에 이동한 흔적이 있는지 확인하여 걸린시간이 덮어씌어지는 것을 방지한다.x-1, x+1, x*2 3번의 위치이동을 하고 graph 인덱스의 값에 현재 위치의 걸린시간 +1 초를 더해 이동한 흔적을 남긴다. 그리고 이동한 위치를 queue에 넣는다. 방문하지 않은 곳은 걸린시간이 0이다. 왜냐하면 graph를 만들..

백준 2667번 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 풀이 미로 찾기와 매우 유사한 문제이다. 다른점은 단지라는 그래프의 개수와 각 단지의 집들 즉, 각 그래프의 노드들의 개수를 오름차순으로 출력하는 문제이다. 그저 그래프를 찾아내서 얼마만큼의 노드들이 연결되어 있는지만 확인하기에 BFS, DFS 둘다 사용이 가능하다. 여기서는 BFS를 사용하였다. import java.io.*; import java.util.*; public class Main { static int[][] graph; st..

백준 2606번 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 문제 풀이 그래프에서 1번 컴퓨터(노드)를 시작점으로 연결되어있는 컴퓨터들은 모두 바이러스에 감염된 것이기에 BFS , DFS 둘다 사용하여 풀 수 있다. 이번에는 DFS를 사용하여 풀었다. 재귀호출 , Stack 두 가지 경우를 둘다 사용해보았다. import java.io.*; import java.util.*; public class Main { static int[][] graph; static boolean[] visited; static i..

백준 2178번 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 BFS를 사용하여 풀었다. 시작점이 (0,0)으로 고정되어있고 각 칸과 칸 사이의 거리는 동일하고 이동할 수 있는 칸들은 서로 연결되어 있기 때문에 결국에는 미로를 그래프로써 본다면 (N,M)까지 가는 거리는 그 높이만큼이 거리라고 볼 수 있다. import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.StringToken..

백준 1260번 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 풀이 DFS와 BFS의 기본적인 문제 보통 DFS는 스택이나 재귀호출 BFS는 큐를 사용한다. import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static Queue card; public static void main..