🔗 문제 링크 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 📖 풀이 과정 - DFS 관련 유형의 문제입니다. - 각 도시는 무조건 연결되어있다는 전제조건이 있습니다. - 그래서, 어떤 도시에서 어떤 도시를 방문할 수 있는지 없는지는 신경쓰지 않아도 됩니다. - 하지만, 결국에는 시작했던 도시에 다시 와야 합니다. - 그래서, 메소드의 매개변수로 start한 도시가 계속해서 함께 포함됩니다. - depth 변수가 도시의 총 개수와 같아질 경우에는 현재 있는 도시에서..
🔗 문제 링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 📖 풀이 과정 - 재귀를 이용하여 DFS 방식으로 풀었습니다. (BFS방식으로 풀어도 됩니다.) - 기본적으로 배열의 값이 1이면서, 방문하지 않은 곳을 기준으로 DFS를 사용합니다. - 이후, DFS 재귀내에서 count 변수를 통해 연결되어 있는 Node를 탐색하여 count 변수를 반환합니다. - Main 메소드에서 dfs() 메소드의 시작점 이 곧 count 변수에 포함되기 때문에 초기화를 1로 합니다. - 어차피, 총 단지수는 List의 s..
🔗 문제 링크 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 📖 풀이 과정 - DFS 를 이용한 그래프 유형의 문제입니다. (재귀를 이용한 DFS로 풀었습니다.) - 다른 그래프 문제와의 차이를 보자면, 늑대와 양의 수를 매번 확인하여 계산된 값을 구해야 합니다. - 이를 위해, dfs() 메소드를 호출하기 위해서는 '.', 'v', 'o' 이어야 하며 방문하지 않은 곳이어야 합니다. - dfs() 메소드가 끝날 때마다 늑대의 수가 양의 수 이상일 경우에는 양은 0이 되고 그 반대의 경우에는 늑..
🔗 문제 링크 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 📖 풀이 과정 - DFS, BFS 유형의 구현문제입니다. (저는, DFS를 재귀로 구현했습니다.) - (0,0)이 입력 받을 때까지 과정을 반복합니다. - DFS 메소드에서 가로, 세로, 대각선 방향의 섬들을 모두 함께 탐색합니다. - DFS 메소드를 호출한 횟수를 count변수에 담아야 합니다. - 주의할 부분은 일반적인 x가 h와 비교를 , y는 w 변수와 비교를 해야하는 것입니다. - 이외에는 일반적인 DFS 메소드를 구현하시면 풀 수 ..
🔗 문제 링크 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 📖 풀이 과정 - 이분탐색 유형의 문제입니다. - 메소드를 분리하면, binarySearch() 메소드는 적절한 거리 길이를 구하는 메소드, canInstall() 메소드는 집의 개수를 세는 메소드입니다. - binarySearch() 메소드 내부를 보면, 이분탐색의 알고리즘을 적용합니다. - 입력받은 c 변수와 비교하여 변수 answer에 담아 반환합니다. - canInstall() 메소드 내부..
🔗 문제 링크 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 📖 풀이 과정 - 백트래킹을 활용한 구현 문제입니다. - 배열의 값을 입력 받을 때 치킨집에 해당하는 값을 치킨리스트에, 집에 해당하는 값을 집 리스트에 담습니다. - 이후, 백트래킹 방식을 활용하여 치킨 리스트에 있는 값들을 순회합니다. - 만약 인덱스 값이 m값이 된다면, 그때서야 집 리스트에 있는 값들과 순회하면서 치킨 거리 및 도시의 치킨 거리값을 구합니다. - 구한 도시의 치킨 거리의 최소값을 갱신하면서 문제를 진행합니..
