[프로그래머스] 86971 전력망을 둘로 나누기 - JAVA - Lv2문제https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 분석조건하나의 트리형 전력망이 있다 (노드 + 간선)전선을 하나 끊어서 두 개의 네트워크로 나눌 수 있는데 이때 두 네트워크의 노드 수 차이를 최소로 만들어 차이를 출력풀이방법트리를 입력받은 후 간선마다 돌아가며 DFS를 수행하면 된다.하나의 트리로 연결되어있고, 전체 노드의 수를 알고 있으므로 간선의 두 노드 중 하나에서만 DFS를 돌리면 나머지 네트워크의 노드 수도..

[백준/BOJ] 1240 노드사이의 거리 - JAVA - 골드5문제https://www.acmicpc.net/problem/1240문제 분석조건노드 N개로 구성된 트리(간선 N-1개)가 주어진다.각 간선에는 거리(가중치)가 있다.M개의 쿼리가 주어지고, 각 쿼리마다 두 노드 사이의 거리를 출력해야 한다.풀이방법트리에서 두 노드 사이의 경로는 항상 유일하다.따라서 각 쿼리에 대해 DFS나 BFS로 시작 노드부터 도착 노드까지의 경로를 찾아, 누적 거리만 계산하면 된다.코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { s..

[백준/BOJ] 1149 RGB거리 - JAVA - 실버1문제https://www.acmicpc.net/problem/1149문제 분석조건N개의 집이 일렬로 있다.각 집은 빨강, 초록, 파랑 중 하나로 칠해야 한다.서로 인접한 두 집은 같은 색으로 칠할 수 없다.모든 집을 칠하는 비용이 주어질 때, 전체 최소 비용을 구하는 문제이다.풀이방법i번째 집을 칠할 때는, 바로 앞 집과 같은 색을 사용할 수 없다는 제약이 존재한다.따라서 i번째 집을 빨강으로 칠한다면, i-1번째 집은 초록이나 파랑으로 칠해야 한다.이 원리를 바탕으로, 현재 집을 어떤 색으로 칠할지를 결정할 때는 이전 집에서 가능한 두 가지 색 중 더 적은 비용을 선택하여 누적해나가는 방식으로 최소 비용을 구할 수 있다.점화식에 따라 각 집을 어..

[백준/BOJ] 12946 하노이의 탑 - JAVA - Lv2문제https://school.programmers.co.kr/learn/courses/30/lessons/12946 문제 분석조건한 번에 한 개의 원판만 옮길 수 있다. 큰 원판이 작은 원판 위에 올라갈 수 없다.세 개의 기둥을 이용해 모든 원판을 시작 기둥에서 목표 기둥으로 옮겨야 한다.풀이방법원판이 1개일 경우, 시작 기둥에서 목표 기둥으로 바로 옮긴다.원판이 N개일 경우, 가장 큰 N번 원판을 목표 기둥으로 옮기기 위해 다음을 반복한다.N-1개의 원판을 보조 기둥으로 옮긴다.N번 원판을 목표 기둥으로 옮긴다.보조 기둥에 있던 N-1개의 원판을 목표 기둥으로 옮긴다.이 과정을 재귀적으로 반복하여 모든 원판을 이동시킨다.코드import ja..

[프로그래머스] 92343 양과 늑대 - JAVA - Lv3문제https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 분석조건2진트리 각 노드의 양이나 늑대가 1마리씩 존재한다.양의 수가 늑대의 수보다 작거나 같으면 양은 잡아먹힌다.루트노드는 양이다.트리를 탐색하며 최대한 많은 양을 모을 때 양의 수를 출력.풀이방법BFS인데 일반적인 BFS가 아니다.방문처리하는 방법이 핵심이라고 생각하는데, 다른 BFS처럼 지금 노드의 번호를 저장하는 것이 아니라 양의 수, 늑대의 수, 방문 가능한 노드들을 ..

[프로그래머스] 43162 네트워크 - JAVA - Lv3문제https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 분석조건배열로 연결관계가 포함된 컴퓨터가 있다.컴퓨터끼리 직접, 혹은 간접적으로 연결되어 있으면 같은 네트워크라 하는데 전체 네트워크의 수를 구하는 문제풀이방법0번 컴퓨터부터 n-1번 컴퓨터까지 반복문을 돌면서 방문하지 않은 컴퓨터에서 BFS를 돌린다.코드import java.util.*;class Solution { public int solution(int n, int[]..