세상을 바꾸는 데이터

① 문제 링크 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net ② 알고리즘 분류 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 ③ ★문제풀이 Point★ - 순환선에 속하는 역은 깊이 우선 탐색(dfs) 실시 - 각 역과 순환선 사이의 거리는 너비 우선 탐색(bfs) 실시 ④ 풀이 이 문제는 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구하는 문제다. 1. 순환선에 속하는 역 구하기 각 역과 ..

문제 링크: https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 ★문제풀이 Point★ 1. 총 돌의 개수는 고정이다. 2. 총 돌의 개수가 3의 배수가 아니라면 어떤 수를 쓰더라도 모든 그룹에 있는 돌의 개수를 같게 만들 수 없다. 풀이 과정: 이 문제는 강호가 모든 그룹에 있는 돌의 개수를 같게 만들려고 할 때 가능하면 1을, 불가능하다면 0을 출력하는 문제이다. 먼저 돌의 총합이 ..

문제 링크: https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 앞서 풀은 이모티콘 문제와 유사하다. 이모티콘 문제는 다음 포스트를 참고하자. https://data-flower.tistory.com/80 [백준 14226번] 이모티콘 - 파이썬 문제 링크: https://www.acmicpc.net/problem/1422..

문제 링크: https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 유형: 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 다이나믹 프로그래밍(DP)로 풀지 않고 딕셔너리를 이용한 bfs로 풀었다. bfs 대부분의 문제는 방문 표시를 가능한 전체 인덱스 수만큼 만들어서 해결하는데, 이 문제는 다르다. 이 문제는 현재 이모티콘의 개수와 클립보드에 있는 이모티콘 개수 2가지를 이용해 bfs로 풀어야 한다. 방문..

문제 링크: https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 숨바꼭질 문제를 응용한 문제로서 난이도가 조금 높아졌다. 기본 숨바꼭질 문제는 다음 링크를 참조하자. https://data-flower.tistory.com/78 [백준 1697번] 숨바꼭질 - 파이썬 문제 링크: https://www.acmicpc.net/problem..

문제 링크: https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 유형: 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 너비 우선 탐색(BFS)을 이용하여 해결할 수 있다. 이 문제의 포인트는 바이러스가 낮은 번호부터 증식한다는 점이다. 이는 정렬을 이용하자. 낮은 번호부터 증식하므로, 초기에 큐에 원소를 삽입할 때는 낮은 바이러스의 번호부터 삽입한다. 이후에 BFS를 수행하여 방문하지..