🛵꾸준한 꿈틀꿈틀

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이해 풀이에 앞서 문제를 이해해보자 토마토의 익은 상태가 1초마다 1칸씩 전이되는 상황이고 전체 토마토에 전이되는데 걸리는 최소 시간을 출력해야한다 결국 탐색을 진행해야하고, 각 좌표에 최소 시간을 기록해야하므로 BFS를 이용해야한다 BFS를 진행하며 cost를 기록하고 탐색 종료 후에 cost 중 가장 큰 값을 출력하면 된다 풀이 여기서 방문처리는 익은 토마토 여부로 한다 = 1..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이해 해당 문제는 2차원 배열로 주어지는 map을 탐색하여 연결된 지역을 찾는 문제이다. 즉 map을 순회하며 방문처리되지 않은 좌표가 있다면 해당 좌표를 기준으로 인접한 좌표를 모두 방문처리한다. 이렇게하면 연결된 지역은 모두 방문처리될 것이고 map을 순회 중에 방문되지 않은 좌표를 찾는다면 새로운 지역의 발견을 의미한다. 따라서 map을 순회하며 방문되지 않은 좌표를 찾을 시 해당 좌표를 시작..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 이해 문제 풀이에 앞서 문제를 이해해보자. 연결 요소(Connected Component)는 연결된 정점의 집합을 의미한다. 다음 이미지에서의 연결 요소는 4개이다. 따라서 해당 문제는 그래프 탐색을 통해 연결된 정점을 모두 방문처리하고 방문처리 되지 않은 정점이 발견되면 새로운 연결 요소임을 의미한다. 풀이 전체 노드(1~N)를 순회..