https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색, 시뮬레이션 설명 외부 공기와 접촉하는 칸이 두 곳 이상이면 치즈가 녹습니다. 이때, 모든 치즈가 녹으려면 얼마만큼의 시간이 필요한지 구하는 문제입니다. DFS, BFS 중 어느것을 사용해도 무방하나, 저는 DFS를 사용하여 풀이하였기에, 본 포스팅에선 DFS를 사용한 접근법과 풀이를 서..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 탐색, 그래프 이론, 다이나믹 프로그래밍 설명 DFS를 사용하여, 직전 파이프의 형태 (가로, 세로, 대각선)을 참고하여 풀이할 수 있는 문제입니다. 처음엔 DFS 없이 DP만을 사용하여 풀이하려고 했으나, 생각보다 잘 되지 않아서, 마침내 그래프 탐색 문제인걸 깨닫고 푼 문제였습니다. 소스코드 전체 소스코드 import java.io...

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색 설명 이전에 많이 해보았던 상하좌우 4방향으로 이동하는 BFS 문제에, 체스의 나이트 방향으로 움직일 수 있는 조건이 더해진 문제입니다. 단, 나이트 이동의 경우 k번이라는 제약조건이 있으므로, 말 이동을 k번 이하로 사용하면서 최단 경로로 목표지점에 도달하는게 핵심입니다. 소스코드 Data Class - P..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 난이도 : 골드4 태그 : 자료구조, 그래프 이론, 그래프 탐색, 분리 집합 설명 파티에 진실을 아는 사람이 포함되어 있으면, 그 파티에 참여한 사람들은 모두 진실을 알고 있다고 간주하고, 진실을 알고 있는 사람들이 하나도 포함되어 있지 않는 파티를 카운트하는 문제입니다. 문제 태그에도 명시되어 있듯이 그래프 탐색(DFS/BFS)를 통해서도 풀 수 있지만, 분리 집합 (Union - Find 알고리즘 이용)..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 백트래킹, 깊이 우선 탐색 설명 DFS를 사용한 백트래킹을 사용하여 풀 수 있는 문제 입니다. 아이디어 자체는 빨리 떠올랐는데, 시간초과 때문에 꽤 애먹었던 문제였습니다. 처음엔 방문한 좌표와 사용한 알파벳을 각각 체크하였는데, 생각해보니 사용한 알파벳만 체크해도 되더군요. 사용한 알파벳 역시 ArrayList로 했더니 시간초과가 나..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 난이도 : 골드5 태그 : 그래프탐색, 너비우선탐색, 그래프이론 설명 이전의 포스팅했던 백준 7576번 토마토는 한 층인 평면(x, y축)으로만 이루어졌던과 달리, 7569번 토마토는 복수의 층으로 입체(x,y,z)로 이루어져 있는게 차이점입니다. 이전 포스팅의 코드를 베이스로 약간 변형을 주어 3차원 BFS로 풀이할 수 있으며, 이전 포스팅의 내용이 궁금하신 분은 아래 링..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 좌표 상 각 블록(단지)의 개수가 몇개인지 판단하는 전형적인 그래프 탐색 (DFS / BFS) 문제입니다. 모든 점에 대해 DFS / BFS를 진행하며, DFS / BFS가 진행된 횟수를 카운트하면 됩니다. DFS 및 BFS 중 어느것을 사용해 풀이해도 무방하나, 이전 코테 포스팅에서 DFS는 많이 풀이..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 난이도 : 골드5 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 주변(상하좌우, 대각선 X) 토마토를 익힌다 하였으니, BFS인걸 알 수 있다. 처음엔 초기 토마토 위치로 각각 BFS를 한 사이클씩만 돌리려 하였으나.... 그럴수가 있나..? 하는 생각에 접근법을 달리 하였습니다. 한 사이클이 돌 때마다, x, y값이 -1인 값을 큐에 넣어 확인하여 한 사이클이 돌 때..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색 설명 DFS와 BFS 그래프 탐색 문제이며, DFS와 BFS를 통해 구할 수 있습니다. 그러나, 이 문제에서는 BFS가 보다 적합합니다. DFS의 경우 모든 경로를 확인하며, 그중에서 가장 짧은 경로를 선택하여야 합니다. BFS의 경우는, 처음 마지막 좌표에 도착한 시점의 경로가 가장 짧은 경로입니다. 따라서 단순히 그래프를 탐색하는 것이 목적일때는 DFS..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 난이도 : 실버 3 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 DFS 혹은 BFS를 이용해 연결된 노드의 갯수를 구하는 문제입니다. DFS, BFS 어느 것을 사용해도 무방하나 DFS를 많이 사용해봤기에 이번엔 BFS를 사용해 풀이해보겠습니다. 소스코드 인풋값 저장 val n = readLine()!!.toInt() val bridgeCnt = readLine()!!...