🔗 문제 링크
📌 문제 설명
N x N크기의 농장이 주어지고, 길(R)과 소(K)의 위치가 주어진다.- 각 칸은
(x, y)좌표로 표현되며, 길이 없는 곳은 자유롭게 이동 가능하다. - 길이 존재하는 경우, 해당 방향으로 이동할 수 없다.
- 서로 만날 수 없는 소들의 쌍의 개수를 구하는 문제.
🔍 접근 방식
🔹 1️⃣ 완전 탐색 (모든 쌍을 확인) → 비효율적
- 소(
K)의 최대 개수가10000, 농장(N)의 크기도10000 - 모든 소의 조합을 고려하면
K * K = 10^8→ 시간 초과 발생 가능성 큼 🚨
🔹 2️⃣ DFS를 활용하여 하나의 소에서 모든 소를 탐색
- 특정 소에서 DFS를 실행하여 길이 없는 범위 내에서 이동 가능 여부를 확인
- 만약 특정 소에서 DFS를 돌렸을 때 만날 수 없는 소의 개수를 구하면,
K - 1 - (만난 소의 개수)로 구할 수 있음 ✅
- 이를 모든 소에서 실행하면
K번 DFS 실행으로O(N^2)이하로 가능.
🔹 3️⃣ HashSet을 활용한 빠른 탐색
- 소의 위치와 길의 위치를 빠르게 확인하기 위해
HashSet을 활용 - 길이 있는지 확인하는 과정에서 (x1, y1, x2, y2) 형태로 저장하여 빠르게 접근
- 소의 위치도 (x, y)로 저장하여 O(1) 탐색 가능
📝 코드 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
private static StringTokenizer st;
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N, K, R;
private static Set<String> roads = new HashSet<>();
private static Set<String> cows = new HashSet<>();
private static int[] dix = {-1, 0, 1, 0}; // 상우하좌 방향 탐색
private static int[] diy = {0, 1, 0, -1};
private static int cowCnt, answer;
public static void main(String[] args) throws IOException {
setting();
for (String cow : cows) {
st = new StringTokenizer(cow, ",");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
boolean[][] visited = new boolean[N + 1][N + 1];
cowCnt = 0;
visited[x][y] = true;
dfs(x, y, visited);
answer += cows.size() - 1 - cowCnt;
}
System.out.println(answer / 2); // 쌍으로 계산되므로 2로 나눔
}
private static void dfs(int x, int y, boolean[][] visited) {
for (int i = 0; i < 4; i++) {
int dx = x + dix[i];
int dy = y + diy[i];
if (dx <= 0 || dx > N || dy <= 0 || dy > N) continue;
if (roads.contains(formatRoadKey(x, y, dx, dy))) continue;
if (visited[dx][dy]) continue;
visited[dx][dy] = true;
if (cows.contains(formatPositionKey(dx, dy))) cowCnt++;
dfs(dx, dy, visited);
}
}
private static void setting() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
roads.add(formatRoadKey(x1, y1, x2, y2));
roads.add(formatRoadKey(x2, y2, x1, y1)); // 양방향 저장
}
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
cows.add(formatPositionKey(x, y));
}
}
private static String formatRoadKey(int x1, int y1, int x2, int y2) {
return x1 + "," + y1 + "," + x2 + "," + y2;
}
private static String formatPositionKey(int x, int y) {
return x + "," + y;
}
}✅ 코드 설명
🔹 HashSet을 사용한 탐색 최적화
roads: 길 정보를(x1, y1, x2, y2)형태로 저장하여 빠른 접근 가능cows: 소의 위치를(x, y)형태로 저장하여 O(1) 탐색 가능
🔹 DFS를 이용한 탐색
visited[][]배열을 사용하여 탐색한 경로를 저장cowCnt를 증가시키며 만날 수 있는 소를 계산- 길이 있는 경우
HashSet에서 탐색하여 빠르게 걸러냄
🔹 meetable_cows 활용
cow.size() - 1 - cowCnt를 이용하여 만나지 못한 소의 개수 계산- 모든 소에서 수행 후
answer / 2를 출력하여 최종 쌍의 개수 도출
🧐 수정해야 할 부분 및 최적화 가능성
1️⃣ BFS 알고리즘으로 변경
이 문제는 소들이 서로 연결될 수 있는지 확인하는 문제이므로, 최단 거리 탐색이 중요함.
✅ BFS는 레벨 단위 탐색을 수행하기 때문에, 더 빠르게 연결 관계를 확인할 수 있음.
🚨 DFS는 경로를 끝까지 탐색해야 하므로, 탐색 시간이 더 오래 걸릴 가능성이 높음.
각각의 소의 좌표에서 빠르게 다른 소들에게 접근하여 연결되는 소들의 개수를 파악해야하는 문제.
때문에 한 곳을 중심으로 깊에 찾아내는 DFS 알고리즘은 맞지 않는 구조라고 생각.
실제로 다른 사람들의 BFS 풀이와 비교해보았을때 약 4배정도로 느린 속도를 보여줌.
- BFS는 모든 방향을 동시에 탐색하며 빠르게 다른 소에 도달할 수 있음.
- 최단경로, DFS가 아닐때
- DFS는 경로를 끝까지 탐색해야 하므로, 비효율적인 탐색이 발생할 수 있음.
- 경로가 존재하는지, 백트래킹, 트리탐색, 재귀 관련
✅ 결론
최단 경로를 찾아야 하는 문제에서는 BFS가 더 적합함.
2️⃣ boolean[][] visited의 재사용 가능
현재는 모든 소에서 DFS를 수행할 때 visited 배열을 새로 생성하지만,
이보다는 초기화 후 재사용하는 것이 메모리 효율적이다.
boolean[][] visited = new boolean[N + 1][N + 1]; // 전역 배열로 설정이후 Arrays.fill()을 사용하여 초기화 가능.
3️⃣ String 대신 int[][] 배열로 변경
HashSet<String>을 사용하여 길 정보를 저장하지만,
boolean[N+1][N+1][4] 배열을 사용하면 메모리와 속도를 최적화할 수 있음.
boolean[][][] roads = new boolean[N + 1][N + 1][4]; // 방향별 길 정보 저장이렇게 하면 길이 존재하는지 여부를 roads[x][y][방향]으로 O(1) 조회 가능.
🚀 결론
✅ DFS + HashSet을 활용하여 빠르게 해결
✅ 소의 쌍을 직접 비교하지 않고 DFS로 탐색 최적화
✅ 길 정보를 HashSet에서 관리하여 빠른 접근 가능
✅ 더 최적화하려면 visited 배열을 재사용하거나, boolean[][][] roads로 변환 가능
멋있는 사람 - 일단 하자