목록알고리즘/DFS, BFS (18)

쉬운 프로그래밍

[알고리즘] 프로그래머스 - N으로 표현 - JAVA

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수..
알고리즘/DFS, BFS 2021. 10. 8. 15:38
[알고리즘] 백준 2636 치즈 - JAVA

www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 문제설명 치즈의 모서리(입력 배열에서 0과 맞닿아 있는 부분중에서 바깥부분)이 시간마다 녹는다. 이 때 치즈가 다 녹는 시간과 다 녹기 직전 시간의 치즈의 개수를 구하는 문제이다. 해결방법 처음에는 1인 부분부터 BFS를 돌려서 0과 맞닿아있으면 모서리라고 생각해 그것을 녹여간다는 방향으로 생각했다. 근데 이렇게 하면 치즈 내부에 형성된 모서리를 찾을 수 없다. 그렇기 때문에 무조건 치즈가 존재하지 않는 (0,0)부터 ..
알고리즘/DFS, BFS 2021. 3. 30. 00:12
[알고리즘] 백준 16234 인구 이동 - JAVA

www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 설명 상하좌우로 인접해 있는 땅과의 인구수 차이가 L이상 R이하면 국경선이 열린다. 인접한 땅만을 통해서 형성된 그룹을 연합이라 한다. (BFS 또는 DFS를 통해서 탐색이 되는 범위) 연합 내의 모든 나라는 동일한 인구수를 가지도록 사람들을 이주시킨다. (소수점 제외) 인구 이동을 더 이상 할 수 없을 때까지 사람들을 이주 시켜야 할 때, 총 몇번의 인구 이동이 이루어질지를 구하는 문제이다..
알고리즘/DFS, BFS 2021. 3. 27. 17:57
[알고리즘] 백준 14502 연구소

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 벽을 무조건 3개 세웠을 때 가장 최소의 칸만큼 바이러스가 퍼지는 경우를 구하는 문제이다. 입력범위가 매우 작다(80) ,,,// 제발 문제풀기전에 입력 범위 숙지하는 습관좀... 입력범위가 작기 때문에 3개의 벽을 세우는 모든 경우에 대하여 구해도 시간초과가 나지 않는다. 그러므로 백트래킹을 통해 모든 경우에 대해 3개의 벽을 세우고, depth가 꽉 차면 바이러스를 퍼뜨린다(bfs) 즉 이 문제는 dfs + bfs 모두..
알고리즘/DFS, BFS 2021. 3. 18. 02:41
[알고리즘] 백준 16918 봄버맨 - JAVA

www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 알고리즘보다는 구현 과정에서 애를 먹었던 문제였다. 풀이에 가장 기초가 되는 생각은 홀수 시간에는 폭탄을 세팅하고, 짝수 시간에는 폭탄을 터뜨려야 한다는 것이다. 폭탄이 세팅되었다면, 세팅된 시각에 맞게 터뜨려지거나 옆칸의 폭발에 휘말려서 없어지는 로직을 짜야하는데 나는 폭탄입력시간만 가지고 노는 2차원 배열을 만들어서 했다. 정답 소스코드 import java.io.BufferedReader; import java.io.IOE..
알고리즘/DFS, BFS 2021. 3. 16. 16:52
[알고리즘] 백준 1697 숨바꼭질 - JAVA

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 입력으로부터 받은 start 지점부터 end 지점까지 -1, 1 *2 방향으로 bfs를 돌리면 된다. 주의해야할 점은 5 9가 입력으로 주어지는 경우 5 -> 10 -> 9와 같은 상황이 있다. 나는 처음에 그래프 배열을 초기화할때 인덱스값을 입력제한범위만큼 넣어주어 해결하였다. 소스코드 import java.io.BufferedReader; import java.io.IOExcept..
알고리즘/DFS, BFS 2021. 3. 4. 14:51
[알고리즘] 백준 2146 다리만들기

www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 아이디어를 생각 해내면 그렇게 어렵지는 않은 문제같다... 물론.. 생각해내면.. 입력으로 지도의 2차원 배열 정보가 주어진다. BFS를 통해서 한 섬에서 다른 섬을 이어주는 최소비용을 구해야한다. 이 문제를 풀기 위해서는 섬과 바다가 맞닿아있는 지점을 반복문을 통해 BFS를 돌려 최소의 거리를 찾아야한다. 여기까지는 어렵지 않게 생각을 했긴 하지만, 해당 지점이 섬과 맞닿아있는지 판별하는 것과 다른 섬에 도착하여 ..
알고리즘/DFS, BFS 2021. 3. 3. 21:12
[알고리즘] 프로그래머스 - 네트워크

programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr import java.util.*; class Solution { public int solution(int n, int[][] computers) { boolean visited[] = new boolean[n]; int answer = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { answer += bfs(computer..
알고리즘/DFS, BFS 2021. 1. 25. 17:09
Prev 1 2 3 Next