백준8 [백준]11724_연결 요소의 개수_BFS Java 풀이(반례 포함) 사이트 링크 11724번: 연결 요소의 개수 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 개념 및 풀이 그래프의 정점만큼 for문을 돌면서 BFS로 탐색하여 그 정점과 이어졌는지 확인한다. visit[] : 이미 이어졌는지 확인했다면 1, 아니면 0 for문 아직 이어지지 않은 정점이라면 - 정점과 이어진 정점 확인하는 bfs() 함수 이을 수 있는 모든 정점 잇기 이을수 있는 것 다 이었는데도 안이어진 정점은 같은 무리에 속하지 않는 것-> .. 2023. 9. 12. [백준]20413_MVP 다이아몬드 (Easy)_그리디 Java 풀이 20413번: MVP 다이아몬드 (Easy) 20413번: MVP 다이아몬드 (Easy) 입력된 MVP 등급을 달성하기 위한 최대 누적 과금액을 만원 단위로 출력한다. www.acmicpc.net 풀이 각 월의 최대 금액은 그 등급의 최대 등급인데, 이전달의 영향을 받아 그것을 빼 주어야 한다. ex. 30 60 90 150 BSGG… 1달 2달 3달 4달 … 해당 달의 등급 B S G G … 이전달의 영향을 받은해당 달의 최대 금액 B S-B G-(S-B) G-(G-(S-B)) … 0≤B 2023. 2. 14. [백준]1916_최소비용 구하기_다익스트라 인접행렬, 인접리스트 Java풀이 + 반례 1916번: 최소비용 구하기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 처음에 인접행렬로 풀었더니 애먹은 경우가 있었다. 그래서 총 3가지 풀이를 준비했다. 1. 인접행렬 int [][] map = new int[N+1][N+1]; 2. 인접리스트 ArrayList [] map = new ArrayList[N+1]; 3. 인접리스트 ArrayList 0 1번 풀이 package Graph; // 다익스트라 ( 음이 아닌 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착).. 2023. 2. 8. [백준]1018_체스판 다시 칠하기_Java 풀이 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 4중 for문을 돌며... 맨 위 왼쪽이 B로 시작하는지, W로 시작하는지 두가지 상황으로 나누어서 각각의 경우에 다른 값이 있는 개수를 각각 저장한다. -> 최소값을 비교 왼쪽 위가 B로 시작하는 경우 BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB 와 같은 형태 왼쪽 위가 W로 시작하는 경우 WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW 와 같은 형태 .. 2023. 1. 24. 이전 1 2 다음
