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()!!...

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 인풋값으로 받는 맵 정보를 두 개의 배열로 받아 적록색약이면 R과 G를 같은 색상으로 판단해 DFS / BFS를 돌리고, 적록색약이 아닌 사람이면 그대로 DFS / BFS를 돌려 풀 수 있는 문제입니다. DFS와 BFS 중 어느 것을 사용해도 무방하나, 본 포스팅에서는 DFS를 사용하였습니다. ..

https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 전형적인 그래프 탐색 문제입니다. 그래프 탐색 알고리즘은 DFS(깊이 우선 탐색)과 BFS(넓이 우선 탐색)으로 풀 수 있는 문제입니다. DFS와 BFS중 어느 걸 사용하던 무방하지만, 저는 DFS를 사용하도록 하겠습니다. 소스코드 var n = 0 var m = 0 var c..