본문 바로가기

dfs34

[백준] 14888번 연산자 끼워넣기 JAVA (자바) 풀이 문제 14888번 : N개의 수열 (A1, ... , AN) 주어진다 수 사이에 끼워넣을 수 있는 N-1개의 연산자 (+ 덧셈, - 뺄셈, × 곱셈, ÷ 나눗셈) 주어진다 숫자 순서 바꿀 수 X, 연산자 순서 바꿀 수 O : 우선순위 무시하고 앞에서부터 계산 나눗셈은 몫만 구하고, 음수를 양수로 나눌 때에는 숫자끼리만 나누고 몫에 -만 붙여준다 (=음수처리) : 결과식 최대인 것과 최소인 것을 구해라 [입력] : 첫 줄에 수열 개수 N : 둘째 줄 N개의 수열 : 연산자 개수 ( +, -, ×, ÷ 순서 ) [출력] : 식 최댓값 첫째줄에, 식 최솟값 둘째줄에 출력 [알고리즘] 모든 경우를 분석해야 하는구나 = 완전 탐색 = 브루트 포스 연산자의 조합을 이용해야 한다 = 순열 순열을 쉽게 구하기 위해서는.. 2023. 10. 29.
[백준] 7576번 토마토 JAVA (자바) 풀이 문제 7576번 (2차원 토마토 문제) : 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 구하는 프로그램 : 토마토는 격자모양 상자의 칸에 하나씩 넣은 다음 상자들을 수직으로 쌓아 올려서 창고에 보관 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다 : 익은 토마토과 인접하면 익지 않은 토마토들 영향을 받는다 인접한 곳 = 상, 하, 좌, 우 4가지 방향에 있는 토마토 [입력] : 첫 줄에는 상자 가로크기 M, 상자 세로 크기 N : 둘째 줄부터는 저장된 토마토들의 가로 세로 정보 : 1 = 익은 토마토, 0 = 익지 않은 토마토, -1 = 토마토가 들어있지 않은 칸 [출력] : 여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력 : 저장될 때부터 모든 토마토가 익어있.. 2023. 9. 21.
[백준] 7569번 토마토 JAVA (자바) 풀이 문제 7569번 (bfs, 3차원 토마토 문제) :  토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 구하는 프로그램 :  토마토는 격자모양 상자의 칸에 하나씩 넣은 다음 상자들을 수직으로 쌓아 올려서 창고에 보관    상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다 :  익은 토마토과 인접하면 익지 않은 토마토들 영향을 받는다    인접한 곳 = 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토     [입력] :  첫 줄에는 상자 가로크기 M, 상자 세로 크기 N, 쌓아올려지는 상자의 수 H (단, 2 ≤ M,N ≤ 100, 1 ≤ H ≤ 100)  :  둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보  :  1 = 익은 토마토, 0 = 익지 .. 2023. 9. 21.
[백준] 11725번 트리의 부모 찾기 JAVA (자바) 풀이 문제 11725번 :  트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램     [입력] :  첫째 줄에 노드의 개수 N :  둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점   [출력] :  2 부터 N 노드까지 부모 노드 순서대로 출력    DFS  현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 Stack 혹은 재귀함수로 구현 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가더 이상 갈 수 없게되면 다른 방향으로 다시 탐색 진행모든 노드를 방문하는 경우에 사용  ArrayList   - 본 코드에 arr 가 아닌 arraylist를 사용한 이유는 메모리초과 때문이다 - 배열과 차이점 : 배열은 크기가 고정, ArrayList는 크기가 가변적   - Arr.. 2023. 9. 20.
[프로그래머스] Lv.2 미로 탈출 JAVA 풀이 문제 Lv.2 미로 탈출 : 직사각형 격자 형태의 미로 벽으로 된 칸 이동 불가 통로로 된 칸 이동 가능 : 출력 = 입구-레버-출구까지 거치는 최소의 탈출 길이 (탈출할 수 없다면 -1 출력) : 출발 레버 출구 모두 따로따로 입구 → 레버 열기 위해 방문 → 나가기 위해 출구 방문 순으로 미로를 탈출한다 : 미로를 나타내는 문자열배열 = maps maps 자체는 길이가 5 ~ 100 maps 배열 중 한 묶음은 5개의 문자로 이루어짐 (S: 시작, E: 출구, L: 레버, O: 통로, X: 벽) Ex) maps = ["SOOOL", "XXXXO", "OOOOO", "OXXXX", "OOOOE"] 이때 maps의 길이는 5이다 [설명] BFS 현재 정점에 연결된 가까운 점들부터 탐색 Queue를 사용해.. 2023. 9. 19.
[백준] 7562번 나이트의 이동 JAVA (자바) 풀이 문제 7562번 (bfs) :  나이트는 몇 번 움직이면 칸으로 이동할 수 있을까?    [입력] :  첫째 줄에는 테스트 케이스 묶음 개수  :  테스트 케이스 한묶음 당 3개의 줄이 있다 :  첫째 줄에는 체스판의 한 변의 길이 (크기 1 × 1) :  둘째 줄에는 나이트가 현재있는 칸 위치 :  셋째 줄에는 나이트가 이동하려는 칸 위치   [출력] :  각 테스트 케이스 묶음마다 나이트의 최소 이동 횟수 출력   [설명]  BFS    현재 정점에 연결된 가까운 점들부터 탐색  Queue를 사용해서 구현     java.awt.Point  -  Point 클래스는 좌표 상의 위치를 나타내는데 사용-  x와 y좌표값을 저장하기 위한 멤버변수를 갖는다 Field SummaryModifier and Ty.. 2023. 9. 17.
[백준] 11724번 연결 요소의 개 JAVA (자바) 풀이 문제 11724번 : 연결 요소의 개수 구하기 [입력] : 첫째 줄에 정점의 개수 N, 간선의 개수 M : 둘째 줄부터 M개의 줄에 간선의 양 끝점 u, v(1 ≤ u, v ≤ N, u ≠ v) (같은 간선은 한 번만) [출력] : 연결 요소의 개수를 출력 [설명] DFS 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 Stack 혹은 재귀함수로 구현 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색 진행 모든 노드를 방문하는 경우에 사용 [문제 과정] 입력 1 2 2 5 5 1 3 4 4 6 출력 2 출처 : https://aeunhi99.tistory.com/59 if(!visit[i]){ dfs(i); } → if문 시작 dfs(1).. 2023. 9. 16.
[백준] 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.

티스토리툴바