반응형 전체 글147 [백준] 2839번 - 설탕 배달 (Java) https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 재귀나 반복문으로 푸는 문제가 아니다. 따라서 수들을 늘어서놓고 법칙을 찾아야 한다. N 3 4 5 6 7 8 9 10 11 12 봉지수 1 2 N / 5 1 2 N % 5 3 4 0 1 2 3 4 0 1 2 N 13 14 15 16 17 18 19 봉지수 3 N / 5 2 3 N % 5 3 4 0 1 2 3 4 1. 법칙성을 찾기 위해 N/5와 N%5의 값들을 구해본다. N 3 4 5 6 7 8 9 10 .. 2022. 9. 14. [백준] 1707번 - 이분 그래프 (Java) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. 먼저 이분그래프에 대해 알아보자. 2. 인접한 정점은 다른 색상으로 저장하자. (1 or 2) 3. 방문하려는데 동일한 색상이 이미 칠해져 있으면 이분그래프가 아니다. 4. DFS(정점번호, 색상)을 넘겨주자. import java.util.*; /* [백준] 1707번 - 이분 그래프 (Java) */ public class Main { static int K, V, E; static in.. 2022. 9. 13. [백준] 7562번 - 나이트의 이동 (Java) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. BFS 탐색으로 최소이동거리를 구하는 문제이다. 2. TC가 여러개이므로 매번 맵을 초기화 해야 한다. 3. 누적거리는 map[][]에 탐색하면서 업데이트 한다. 4. 8방향으로 탐색이 가능하다. import java.util.*; /* [백준] 7562번 - 나이트의 이동 (Java) */ public class Main { static int N, M; static int map[][];.. 2022. 9. 13. [백준] 14502번 - 연구소 (Java)(△) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 바이러스가 퍼지는 걸 막으려면 벽을 세워야 하는데 벽의 개수는 3개이다. 2. 바이러스가 상하좌우로 번질 수 있다고 하니 BFS에서 큐에 넣은 것은 바이러스의 위치이다. 2-1. BFS 호출 전에 for문을 돌려서 바이러스(2)를 다 큐에 넣자. 3. 이 문제는 탐색을 2번을 해야 한다. (벽 3개를 세우는 경우의 수, 바이러스 확산의 경우의 수) 3-1. 벽 3개를 완전탐색(DFS)해서 하나씩 세우다가.. 2022. 9. 12. [백준] 1697번 - 숨바꼭질 (Java) https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 1차원 그래프이다. 2. N의 위치에서 할 수 있는 액션은 3개이다. 2-1. nx = 2 * x 2-2. nx = x+1 2-3. nx = x - 1 3. BFS로 위 3개 액션을 for(1 to 3)문으로 돌려서 탐색한다. 4. 방문거리는 visited 배열에다가 이전거리+1을 해서 기록하고, 방문한 노드는 스킵한다. 5. N과 K가 같을 때 BFS 수행 전에 .. 2022. 9. 8. [백준] 1520번 - 내리막 길 (Java) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. map에는 높이 정보가 주어지고, 탐색은 상하좌우로만 가능하다. 2. 경로를 찾는데 높이가 지금보다 낮은 쪽으로만 이동 가능한 경로를 찾는다. 3. 가능한 경로의 개수를 찾는다. 4. dfs 파라메터로 좌표 정보를 넘겨준다. import java.util.*; /* [백준] 1520번 - 내리막 길 (Java) */ public class Main { int N, M; int A[][]; bool.. 2022. 9. 7. [백준] 7576번 - 토마토 (Java) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 익은 토마토는 1, 안익은 토마토는 0, 빈칸은 -1로 주어진다. 2. 익은 토마토의 상하좌우로 영향을 줘서 안익은 토마토가 하루가 지나면 익게 된다. 3. bfs 탐색으로 상하좌우로 탐색할 때 0이면 1로 바꾸고 탐색을 계속한다. 3-1. 상하좌우 검색 후에 누적거리+1 을 하자. 4. 출발점이 없으니 메인함수에서 for문을 돌려서 1이 나오면 bfs를 호출하자. 5. 0이.. 2022. 9. 7. BFS 알고리즘(너비 우선 탐색) ※ 그래프 용어 - 정점(vertex) : 그래프 안의 노드 - 간선(edge) : 각 정점을 잇는 선 - 인접(adjacent) : 간선으로 연결된 정점 - 이웃(neighbor) : 인접한 정점 BFS(Breadth First Search)로 줄여 부르는 너비 우선 탐색은 그래프를 탐색하는 방법이다. 깊이 우선 탐색과 달리 너미 우선 탐색은 재귀를 쓰지 않는다. 대신 큐로 문제를 해결한다. 큐는 FIFO로 먼저 들어간 데이터를 우선 처리한다. * 너비 우선 순회 알고리즘 1. 그래프 내 아무 정점에서 시작한다. 이 정점을 "시작 정점"이라 부른다. 2. 시작 정점을 방문 배열에 추가해 방문 표시를 한다. 3. 시작 정점을 큐에 추가한다. 4. 큐가 빌 때까지 실행하는 루프를 시작한다. 5. 루프 안에.. 2022. 9. 6. [백준] 2178번 - 미로 탐색 (Java)(◎) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1. 미로에서 처음에서 끝까지 가는 최단거리를 구하는 문제이다. 2. 미로 입력에 공백이 없으므로 한줄 씩 string 문자열로 받고, 한글자씩 배열로 저장한다. 3. 방문체크를 위한 visited 배열을 준비하고, 첫 시작인 (1, 1)을 true로 설정한다. 4. BFS 알고리즘으로 상/하/좌/우로 탐색해서 1이면 이동하고 0이면 스킵한다. 5. 최단거리를 구하기 5-1. map 배열의 다음 탐색지에 누적거리+1을 덮어쓰면서.. 2022. 9. 6. 이전 1 ··· 12 13 14 15 16 17 다음 반응형
