[Algorithm/BOJ] 7569 - 토마토 (BFS) Swift
문제풀이: 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. -> 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 6가지 방향으로 탐색하여 토마토를 익힌다. 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다. -> 아래의 그림과 같이 상자에는 익지 않은 토마토, 익은 토마토, 빈 칸이 존재하고 3차원 배열을 이용한다. 정수 1은 익은 토마토, ..
2021. 2. 23.
[Algorithm/Programmers] 섬 연결하기 Swift
섬 연결하기 Level 3 문제 풀이: n개의 섬을 최소 비용으로 모든 섬이 통행이 가능하도록 만든다. -> 크루스칼 알고리즘을 이용한다. 🍎 크루스칼 알고리즘 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키는 것이다. 1. 비용을 기준으로 오름차순으로 정렬한다. 2. 간선을 차례로 확인하면서 사이클이 발생하는지 확인한다. 2-1. 사이클이 발생하지 않으면 최소 신장 트리에 포함한다. 2-2. 사이클이 발생하면 PASS 3. 모든 간선에 대하여 2번을 반복한다. 비용으로 정렬을 한 배열: [[0, 1, 1], [1, 3, 1], [0, 2, 2], [1, 2, 5], [2, 3, 8]] 같은 사이클인지 확인하기 위해서 Parent 배열을 만듭니다. 집합에 포함되어 있지 ..
2021. 2. 2.