문제 출처 : https://www.acmicpc.net/problem/1012
일단 필자는 입력 코드의 예제가 크지않다면, 이해를 위해 도식화 하는 편이다.
따라서, 해당 문제도 도식화 하게 되었습니다.
배추 위치의 x,y
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
를 입력 받을 경우를 도식화 해보자.
그럼 여기서 카운팅을 하면 되는 것이다.
참고로 이 도식화는 이런 식으로 하라는 예시에 불과합니다.
위 도식화에서, 인접배열(리스트)에서 인접한 경우가 1인 경우에 카운트 1을 하라는 것이 아닙니다. {(0,1),(1,1),(1,0)} 중에서 아무 군데나 흰지렁이를 푼다면, 다 안전한 것입니다.
또한, {(4,2)(4,3)} 둘 중 하나, (2,4)(3,4) 둘 중 하나, (4,5)에 1개,
{(7,4)~(9,5)}중 아무거나 한 군데에 놓게 되면 다 안전한 것입니다.
즉,
0은 길이 막혀져있고, 1은 연결되어있는 길이라고 생각하면 쉽습니다.
따라서, 1은 연결되어있는 통로니까 자연스레 지나갈 수 있고, 0은 못가서 cnt++를 해주는 것이라고 이해하면 쉽습니다.
만약, 필자의 설명이 부족하다면, 좀더 자세히 도식화된 설명을 보여주는 좋은 블로깅을 하신 분의 링크를 남기겠습니다. --> https://lotuus.tistory.com/98
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
static int T, M, N, K, count;
static int[][] field;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
field = new int[N][M];
visited = new boolean[N][M];
for (int k = 0; k < K; k++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
field[x][y] = 1;
}
count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (dfs(i, j)) {
count++;
}
}
}
System.out.println(count);
}
}
public static boolean dfs(int x, int y) {
if (x < 0 || x >= N || y < 0 || y >= M || visited[x][y] || field[x][y] == 0) {
return false;
}
visited[x][y] = true;
dfs(x - 1, y);
dfs(x + 1, y);
dfs(x, y - 1);
dfs(x, y + 1);
return true;
}
}
정말 좋은 정보 감사합니다!