https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 난이도 : 골드 2 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 해시를 사용한 집합과 맵 설명 BFS + Map을 사용한 문제입니다. 처음에는 9개 좌표의 방문체크를 어떻게 해야하나... 9차원 visited 배열...?을 생각했으나, 그냥 Map을 사용해 방문체크를 할 수 있습니다. 103 425 786 위의 3x3 퍼즐이 주어졌다면, 이를 103425786와 같이 문자열 혹은 CharArray 형태로 바꿔 생각할 수 있습니다. 즉, map["103..

https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 난이도 : 골드 2 태그 : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 깊이 우선 탐색 설명 0,0 부터 시작하여 해당 칸에 적힌 숫자만큼 상하좌우 중 한 방향으로 이동한다 했을 때, 최대 몇 번 이동할 수 있는지 구하는 문제입니다. 단순히, DFS로 가장 깊은 depth가 어디인지 확인하면 될 것 같았습니다. 네. 아니였습니다. 시간초과가 나버렸으니 시간을 단축시킬 수 있는 테크닉이 필..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프이론, 그래프탐색, 너비우선탐색 설명 앞서 포스팅한 다리만들기 2와 비슷하지만, 1이기 때문에 2보단 쉽습니다. 여러개의 섬이 있을 때, 두 섬을 하나의 다리로 이으면 되기 때문입니다. 접근방법 1) DFS / BFS로 모든 섬을 그룹화한다. 이 때, 모든 섬의 좌표를 저장해놓는다. 2) 1번 과정에서 저장해놓은 각 섬의 모든 좌표를 기준으로 BFS를 수행한다. 2-1..

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 난이도 : 골드 1 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 최소 스패닝 트리 설명 DFS / BFS를 사용해 각 섬을 그룹화 해줍니다. 그리고 각 섬의 모든 점들을 저장해 놨다가, 상하좌우로 방향으로 다리를 만들 수 있는지 확인합니다. 상하좌우 방향으로 현재의 섬을 만난다면 다리를 만들 수 없으며, 다른 섬을 만나..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 최소 스패닝 트리 설명 최소 스패닝 트리의 입문 문제입니다. 응용문제가 아니기에, 연습용으로 제격인 문제네요. 최소 스패닝 트리를 모르신다면 아래 포스팅을 참고해주세요. https://uknowblog.tistory.com/294 [알고리즘] 최소 스패닝 트리 (MST, Minimum Spanning Tree..

https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프이론, 최소 스패닝 트리, 문자열 설명 몇 가지 기믹이 들어간 최소 스패닝 트리 문제입니다. 해당 문제는 랜선을 가장 많이 기부할 수 있는 길이를 찾는 문제입니다. 따라서, 다솜이가 쓸 랜선은 냅두고, 남은 랜선을 줘야 하는데요. 컴퓨터는 연결된 다른 컴퓨터를 타고 들어가 네트워크를 사용할 수 있으므로, 전체 랜선의 길이에서 최소 스패닝 트리의 가중치의 합을..

https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 난이도 : 플래티넘 4 태그 : 자료 구조, 그래프 이론, 데이크스트라, 우선순위 큐 설명 다익스트라가 최단 경로를 찾는 알고리즘이라면, 이번엔 이 다익스트라를 이용하여 K 번째 최단 경로를 찾는 문제입니다. 해당 문제 같은 경우는 우선순위 큐를 활용할 수 있습니다. 우선순위 큐를 내림차순 정렬로 지정하고, 각 우선순위 큐의 크기가 K개를 ..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 분리 집합, 그래프 이론, 그래프 탐색 설명 이미 갔던 도시를 또 다시 방문 및 경유하여 다른 도시로 가도 되므로, 가려고 하는 도시끼리 모두 이어져있는지 (같은 그룹에 있는지) 판단하면 될 것 같습니다. 이 문제에는 분리집합 알고리즘이 유용하게 쓰일 것 같네요. 분리집합 알고리즘을 모르신다면 아래 포스팅을 참고해주세요. https://uknowblog.t..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 꽤 유명한 물통 문제 입니다. 해당 문제에서는 모든 경우의 수를 탐색해야 하므로, DFS, BFS 중 어느것을 사용해도 무방하나 소스코드 import java.lang.StringBuilder import java.util.LinkedList import java.util.Queue..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 모든 정점에 대해 최단거리를 출력하는 문제입니다. BFS를 응용해 풀 수 있겠네요. BFS를 사용한 최단거리 문제는 아래 포스팅을 참고해주세요. https://uknowblog.tistory.com/24 [백준 2178번][Kotlin] 미로 탐색 https://www.acm..