mojo's Blog

문제 링크 => 2146번: 다리 만들기 (acmicpc.net) 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 전형적인 BFS 문제이다. 먼저 대륙별로 숫자를 매기도록 하였다. (1번 대륙, 2번 대륙, ..., i번 대륙) 그리고 각 육지별로 BFS 를 돌려서 바다로 이동이 가능하며 다른 대륙을 발견한 경우 거리를 return 하도록 하여 그 거리들 중에 최솟값이 정답이 된다. 풀이 code #define _CRT_SECURE_NO_WARNINGS #include #include #include #includ..

문제 링크 => 16947번: 서울 지하철 2호선 (acmicpc.net) 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net BFS + DFS 짬뽕 문제이다. 이 문제는 역과 역 사이의 방향이 양방향으로 주어졌고 핵심은 순환이 되는 순환선 즉, 한 역에서 출발해서 계속 가다가 다시 출발한 역으로 돌아올 수 있는 노선을 구분짓는 것이다. 1. 순환선은 DFS 를 활용하여 판별하였다. 판별 방법은 한 역에서 출발해서 계속 가다가 다시 출발한 역으로 돌아올 수 있다는 점을 다음과 같이 해결하..

문제 링크 => 19538번: 루머 (acmicpc.net) 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net BFS 문제이다. 노드와 노드는 양방향으로 이어져 있으며 문제에서 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿는다는 조건을 고려하여 다음 노드로 방문하도록 하는것이 이 문제의 핵심이다. 1. 배열 rumor[x] 를 설정하여 다음 노드로 이동할 때 rumor[next]++ 를 해준다. ( next 사람이 루머를 믿는 수를 1 증가시킴) 2. rumor[n..

문제 링크 => 16929번: Two Dots (acmicpc.net) 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 전형적인 DFS 문제이다. 점마다 DFS를 돌리면서 4번이상 이동함과 동시에 다시 재자리 점으로 돌아올 경우 Yes를 출력하도록 하면 된다. 이때 이동은 점의 색이 같아야 하며 인접하는 경우(좌우상하) 인 경우여야 한다. 그리고 방문처리의 초기화를 위해 별도의 init 함수를 생성하였다. 풀이 code #define _CRT_SECURE_NO_WARNINGS #include #incl..

문제 링크 => 2151번: 거울 설치 (acmicpc.net) 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net BFS 문제이며 문제를 접근한 알고리즘은 다음과 같다. 1. 시작 지점의 방향은 -1로 설정해두고 그 이후로는 0~3(상하좌우) 가 되도록 구현하였다. => 이때, class Light 를 활용하여 위치(x, y), 방향(direction)을 설정하도록 하였고, queue q; 에서 int는 거울을 배치한 갯수를 담도록 설정하였다. 또한 시작지점의 방문처리도 해주었다. (1로 설정하였는..