자바144 [백준] 4963번 섬의 개수 JAVA (자바) 풀이 문제 4963번 : 섬의 개수를 세는 프로그램 : 정사각형으로 이루어져 있는 섬과 바다 지도 : 붙어있는 땅이면 가로, 세로, 대각선 이동가능 = 하나의 섬 섬 개수 = 3 [입력] : 너비 w, 높이 h : h개 줄만큼 지도 표시 (1 = 땅, 0 = 바다) : 위의 과정 반복 : 맨 마지막 줄에는 0 0 [출력] : 각 테스트 케이스의 섬의 개수를 출력 [설명] BFS 현재 정점에 연결된 가까운 점들부터 탐색 Queue를 사용해서 구현 java.awt.Point - Point 클래스는 좌표 상의 위치를 나타내는데 사용 - x와 y좌표값을 저장하기 위한 멤버변수를 갖는다 Field Summary Modifier and Type Field and Description 설명 int x x좌표 int y y.. 2023. 9. 15. [백준] 1260번 DFS & BFS JAVA (자바) 풀이 문제 1260번 : 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램 : 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것부터 방문 : 더 이상 방문할 수 있는 점이 없을 때 종료 : 정점 번호는 1 ~ N [입력] : 첫째 줄에는 정점 수 N, 간선 개수 M, 탐색을 시작할 정점 번호 V : 둘째 줄부터 간선이 연결하는 두 정점의 번호 (정점 사이에 여러 개의 간선이 있을 수 있고 입력으로 주어지는 간선은 양방향) [출력] : V부터 방문된 점을 순서대로 출력 [설명] - DFS 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 Stack 혹은 재귀함수로 구현 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 .. 2023. 9. 14. [백준] 2644번 촌수계산 JAVA (자바) 풀이 문제 2644번 : 부모와 자식 사이 1촌 나와 할아버지 사이 2촌 나와 아버지 형제 사이 3촌 : 주어진 두 사람의 촌수를 계산하는 프로그램 작성 [입력] : 첫째 줄에는 전체 사람 수 n : 둘째 줄에는 촌수를 계산할 두 사람의 번호 r1, r2 : 셋째 줄부터 쌍을 이루는 관계 개수 m : 넷째 줄부터 부모 자식의 관계를 나타내는 x, y [출력] : 두 사람의 촌수를 나타내는 정수 출력 : 두 사람의 친척 관계가 없다면 -1 출력 [DFS 코드] import java.io.*; import java.util.*; public class Main{ static int arr[][]; static boolean visit[]; static int n, r1, r2, m; static int resul.. 2023. 9. 12. [백준] 1012번 유기농 배추 JAVA (자바) 풀이 문제 1012번(dfs, bfs): 배추흰지렁이는 상하좌우 네 방향에 위치한 다른 배추로 이동 가능: 배추흰지렁이가 있는 배추들은 해충으로부터 보호받을 수 있다 : 예) 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅 110000000001000000000000100000000010000000110001110000100111 [입력] : 첫째 줄에는 테스트 케이스 개수 T : 둘째 줄에는 배추 밭 가로 M, 세로 N, 배추 심은 땅 개수 k : 셋째 줄부터 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1) (두 배추의 위치가 같은 경우는 없다) [출력] : 필요한 .. 2023. 9. 11. [백준] 2606번 바이러스 JAVA (자바) 풀이 문제 2606번 : 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다 : 네트워크 상에서 1번과 서로 연결되어 있는 컴퓨터들도 감염 (2번, 5번) : 감염된 컴퓨터들과 연결된 또 다른 컴퓨터들도 감염 (3번, 6번) [입력] : 첫째 줄에는 컴퓨터의 수 (컴퓨터의 수 100 이하인 양의 정수) : 둘째 줄에는 연결된 컴퓨터 쌍의 수 : 셋째 줄부터 쌍을 이루는 컴퓨터 번호 나열 [출력] : 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수 출력 [DFS 코드] import java.util.*; import java.io.*; public class Main { static int arr[][]; static boolean visit[]; static int N, M; static int resul.. 2023. 9. 11. [프로그래머스] Lv.2 무인도 여행JAVA 풀이 문제 Lv.2 무인도 여행 : 지도 = 1 x 1 크기의 사각형으로 이루어진 직사각형 격자 형태 격자 구성 = X, 숫자 (1 ~ 9) - X = 바다 - 숫자 = 무인도 (상, 하, 좌, 우 붙어있는 애들은 하나의 무인도, 대각선은 다른땅) : 하나의 무인도 숫자 합 = 해당 무인도에서 최대로 머무를 수 있는 기한 (오름차순으로 출력) 무인도가 없는 경우 = -1 출력 : maps = 지도 (문자열 배열) [지도 배열 예시] [알고 가기] - 깊이 우선 탐색 - 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 - 스택 or 재귀함수 이용 - 제일 깊게 내려간 뒤 더이상 갈 수 없을 때 옆으로 이동해서 다시 깊게 내려가기를 반복 - 구현 : DFS (간단) > BFS - 검색 속도 : .. 2023. 9. 4. [프로그래머스] Lv.2 광물 캐기 JAVA 풀이 문제 Lv.2 광물 캐기(DFS) - 곡괭이로 광물을 캘 때 피로도 소모 - 캐기 시작하면 한 곡괭이로 광물 5개까지 연속 캐기 - 광물은 주어진 순서대로 캐기 - 광산에 있는 광물 모두 캐거나 사용할 곡괭이가 없을 때까지 캔다 [ 피로도 ] [ 입력 ] - 곡괭이 개수 : picks = [다이아, 철, 돌] (정수 배열) - 광물 순서: minerals (문자열 배열) [알고 가기] - 깊이 우선 탐색- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘- 스택 or 재귀함수 이용 - 제일 깊게 내려간 뒤 더이상 갈 수 없을 때 옆으로 이동해서 다시 깊게 내려가기를 반복- 구현 : DFS (간단) > BFS - 검색 속도 : BFS > DFS (느림) .. 2023. 9. 4. [프로그래머스] Lv.2 요격시스템 JAVA 풀이 문제 Lv.2 요격시스템 : 여러 개구간 x좌표가 있다 이들을 모두 한번씩 관통해야 한다 최소한으로 쏠 수 있도록 최대한 겹쳐 미사일을 쏜다 ▶ targets = [ 1, 4 ], [ 3, 7 ], [ 4, 5 ], [ 4, 8 ], [ 5, 12 ], [ 10, 14 ], [ 11, 13 ] : targets 는 미사일 좌표 범위 좌표는 x좌표로만 이루어져 있고 [s,e] 로 표현 가능 이때, [s,e]는 개구간이다 (즉, 시작지점과 끝지점 미포함) [문제 방식] 1. 끝지점을 기준으로 잡아서 오름차순으로 정렬하고 시작 2. 현재 구간의 끝지점과 다음 타겟의 시작점이 겹치지 않는 순간 count 더 이상 겹칠게 없기 때문에 다음 좌표들의 미사일 쏘고 구간 계산 (이해중요! 일단은 미사일 먼저 쏴놓고 구.. 2023. 8. 28. [백준] 1078번 소수 찾기 JAVA (자바) 풀이 문제 1978번 : 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램 [입력] : 첫 줄에 수의 개수 N. 그 다음으로 N개의 수가 주어진다. [출력] : 소수의 개수를 출력 [코드] import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); br.readLine(); int result = 0; StringTokenizer st = new StringTokenizer(br.readLine()); while (.. 2023. 8. 25. [프로그래머스] Lv.1 덧칠하기 JAVA 풀이 문제 Lv.1 덧칠하기 : 페인트가 비어있는 section 부분의 벽을 덧칠해야한다 롤러의 길이만큼 칠할 수 있고 페인트 덧칠을 최소한으로 측정해 덧칠 횟수를 출력 한다 : n은 벽 길이 m은 롤러 길이 section은 칠해야 할 벽 부분 (예시) n = 5, m = 4, section = {1, 3} 1 2 3 4 5 출력 : 1번째 덧칠 (1 ~ 4 까지 덧칠) 2번째 덧칠 (2 ~ 4 까지 덧칠) return 값 = 2 [코드] class Solution { public int solution(int n, int m, int[] section) { int result = 0; int start = 1; for (int i = 0; i < section.length; i++) { if (start 2023. 8. 24. 이전 1 ··· 8 9 10 11 12 13 14 15 다음
