[백준/알고리즘] 19541번 루머 (골드 4)
BOJ 19541번 풀이 알고리즘 : BFS UCPC 2020 예선 G번 문제인 루머 문제입니다. 한 노드를 봤을 때, 연결된 인접 노드의 절반 이상이 루머를 믿고있다면, 해당 노드도 루머를 믿게 되고, 노드별로 루머를 믿게 된 시간을 출력하는 문제입니다. 여러가지 방법이 있겠지만, 저는 Queue를 두개 이용하여 BFS를 통해 해결했습니다. queue q, qq로 선언을 하였고, 다음과 같이 사용하였습니다. q : "루머를 믿고 있는" 노드번호, 현재 시간을 저장 qq : "q에서의 노드에 인접한" 노드번호, 현재 시간을 저장 먼저 q에 최초 루머를 믿고 있는 노드번호와 시간 0을 입력합니다. while(!q.empty()) 안에는 두개의 while문이 있는데, 첫번째 while문에서는, 현재 q에 들..
[백준/알고리즘] 9019번 DSLR (골드 5)
BOJ 9019번 정수 A, B와 D, S, L, R을 이용하는 간단한 계산기가 있다. 계산기에는 0이상 10000미만의 십진수를 저장하는 하나의 레지스터가 있다. 정수 A를 B와 같게 만들도록 하는 연산 순서를 출력하시오. 연산은 다음과 같다. 풀이 알고리즘 : BFS 일단 시작하기에 앞서, 문제의 시간제한은 6초지만, TC가 많이 들어올 수 있기 때문에, 시간제한에 유의해야한다. 이전 소수경로 문제와 비슷하게, BFS를 이용하여 모든 숫자를 확인하면, BFS의 특성상 깊이(이동 횟수)가 같기 때문에, 가장 먼저 A가 B와 같아지는 경우가 최단 경로이다. 배열에서 좌표를 변환하는 것 대신, 이 문제에서는 4가지 연산이 추가되었는데, 각각 수식으로 표현이 가능하다. i는 현재 확인하고 있는 숫자이고, n..
[백준/알고리즘] 1963번 소수경로 (골드 5)
BOJ 1963번 소수 A, B가 주어진다. 소수 A에서, 각 자릿수 중 하나를 변경해서 다른 소수로 바꿀 수 있다. 소수 A에서 B로 바꿀 때, 변환에 필요한 최소 횟수를 출력하시오. 불가능한 경우 Impossible을 출력한다. 풀이 알고리즘 : BFS, 탐색 먼저 네자릿수 정수가 소수임을 계속 확인해야 하므로, 에라토스테네스의 체를 이용하여, isPrime 배열에 소수인지 아닌지를 저장해 둔다. 이후 시작하는 정수 a를 큐에 입력하고, BFS를 시작한다. BFS에서 다음 소수로 넘어가기 위한 조건은, 각 자릿수(0, 1, 2, 3번째 각각)를 0부터 9까지 하나씩 넣어보면서, 1. 첫번째 숫자를 0으로 바꾸는 경우 - 불가능 2. 해당 숫자가 소수이고, 이전에 탐색하지 않은 경우 - 가능 두 가지 ..
[백준/알고리즘] 11724번 연결요소의 개수 (실버 3)
BOJ 11724번 정점의 개수 n, 간선의 개수 m이 주어졌을 때, 총 연결요소의 개수를 출력하시오. 풀이 알고리즘 : DFS, BFS, ... 그래프 탐색에 관한 문제여서 여러가지 방법이 있겠지만, DFS로 해결하였다. 먼저 n과 m을 입력받고, m개의 간선을 인접행렬인 arr에 입력받았다. (참고) 인접행렬이란? 더보기 인접행렬은 노드의 연결상태를 저장하는 행렬이다. 문제에서는 이차원배열 int arr[][]로 선언하였고, arr[i][j] == 1 이면, i에서 j로 이동하는 간선이 존재한다는 것이고, arr[i][j] == 0 이면, i에서 j로 이동하는 간선이 존재하지 않는다는것이다. 문제에서는 가중치가 없는 그래프이기때문에, 0과 1로만 표현하였고, arr[i][j] = arr[j][i] =..
