🌱1 Day, 1 Commit Wonseok's Record

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 해설 : 케빈 베이컨의 6단계 법칙에 의하면 전 세계의 모든 사람은 지인을 6번만 거치면 모두 아는 사람이라고 한다. N명의 사람과, 연결관계가 주어질 때 각 사람들이 나머지 사람들에 총 몇 단계를 거쳐야 아는 사이가 되는지 구하고 거쳐야하는 단계들의 합 중에 최솟값을 가진 사람을 찾는 문제이다. 풀이 : 사람들간의 연결관계가 주어졌으므로 모든 사람..

https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 해설 : 파란 옷을 입은 병사들과 하얀 옷을 입은 병사들이 뒤엉켜 싸우고 있다. N명의 병사들이 뭉쳐있을 경우 N^2의 힘을 낼 수 있다고 한다. 대각선에 있는 경우는 인접하지 않아 뭉쳐있다고 할 수 없다고 할 때, 파란 병사들와 하얀 병사들의 전투력 총합을 계산하는 문제이다. 풀이 : BFS로 W 또는 B의 병사들을 만났을 때 탐색하고 인접한 병사들의 수를 리턴하여 이 ..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 해설 : 그래프의 노드와 간선정보가 주어질 때, 1번 정점부터 BFS와 DFS로 탐색한 결과를 출력하는 문제이다. 풀이 : 양방향 그래프이므로 0번 노드부터 N-1번 노드까지 연결 관계를 재설정해준 후 이를 BFS와 DFS로 각각 탐색하며 현재 탐색중인 노드를 출력하도록 구현하였다. 소스코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 해설 : N개의 노드로 이루어진 트리가 주어지고, 노드 사이의 거리 M개가 주어질 때, testCase에 대해 노드 사이의 거리를 출력하는 문제이다. 풀이 : 양방향 연결이므로 노드 사이의 거리와 연결 정보를 0번노드부터 N-1번 노드까지 가공한 후 이를 BFS로 탐색하며 원하는 노드가 나왔을 때 거리를 출력한다. 소스코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 해설 : 트리의 노드와 간선정보가 주어질 때, 임의의 두 노드사이의 최대거리를 구하는 문제이다. 풀이 : BFS의 구현은 쉬웠지만 답을 도출하는 아이디어를 떠올리기 힘든 문제였다. 1. 루트노드에서 BFS로 탐색하여 가장 멀리 떨어진 노드를 찾는다. 2. 루트로부터 가장 멀리 떨어진 노드로부터 가장 멀리 떨어진 노드를 찾는다. BFS를 총 2회 실행해야 찾을 수 있는 문제였다. 소..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해설 : 0과 1로 이루어진 2차원 배열이 주어진다. 유기농 배추를 재배하기 위해 1들의 군집(인접한 1들의 집합)마다 배추흰지렁이 한 마리를 방생한다고 할 때, 총 몇 마리가 필요한지 찾는 문제이다. : 풀이 : BFS 또는 DFS로 해결할 수 있는 문제이다. 나는 BFS로 해결하였다. for문으로 배열의 모든 원소를 탐색하며 1인 원소(배추)를 만날 때마다 인접한 모든 원소를, 탐색하고 카운트를 1 증가시..

https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 해설 : 트리형태로 연결되어있는 전력망이 있다. 트리의 간선들 중 하나를 끊어 두 개의 트리로 나눈다고 할 때, 이 두 트리의 노드 개수의 차이가 최소가 되는 값을 찾으면 된다 풀이 : 트리의 탐색은 BFS로 진행했지만 전체적인 구조는 완전탐색으로 진행하였다. 간선들의 정보가 주어진 wires 배열에서 인덱스별로 하나씩 삭제하는 경우를 copy하여 bfs로 탐색하..

https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 해설 : NxN의 2차원 배열의 (0,0) 지점에서 시작하는 사람이 벽으로 막히지 않은 길을 따라 최종 목적지인 (N-1,N-1)까지 도달하려 할 때, 최단거리로 도착할 수 있는 거리를 출력하는 문제이다. 풀이 : BFS나 DFS를 사용하는 문제이다. 나는 BFS가 더 익숙해서 BFS로 해결하였다. 시작점에서..

https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 해설 : 컴퓨터의 개수 n과 컴퓨터 사이의 연결관계인 computers배열이 주어질 때, 컴퓨터들 사이에 몇 개에 독립적인 그래프가 있는지 찾는 문제이다. 풀이 : BFS 또는 DFS로 구현할 수 있는 문제이다. 그래프의 탐색을 구현할 수 있는지 묻는 문제인데 나는 BFS로 풀었다. 우선, 노드 사이의 연결관계인 computers 배열에서 탐색하지 않은 노..