https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
일단 배열로 입력 받는다.
그리고 배열을 돌면서 visit배열을 확인하여 아직 방문하지 않았으면 방문해서, 인접해있는 배열들을 전부 방문하면서 연결된 집을 센다.
좌우,위아래 연결되어있는 집을 찾는거니까 각 연결된 집을 어떤식으로 찾을지 고민해야하는데
각각 (x,y)라고 하고 현재 위치가 (0,0)에 있다고 가정하면
| (0,1) | ||
| (-1,0) | (0,0) | (1,0) |
| (0,-1) |
왼쪽 오른쪽 위 아래 좌표는 각각 저런식으로 될 것이다.
저걸 배열에 각각 저장해주는거다!
아래 코드에서는 11~12줄에 해당한다.
dfs는 상하좌우 좌표를 돌면서, 다음 좌표가 범위 내에 있는지 확인하고 범위 내에 있고, 방문하지 않았고, 집이 있으면 방문한다.
이런식으로 방문하면 끝!
1. DFS
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] arr;
static boolean[][] visit;
static int N;
static int[] dx = {-1,1,0,0}; //좌,우,위,아래
static int[] dy = {0,0,1,-1};
static LinkedList<Integer> res = new LinkedList<>();
static int cnt =0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
arr = new int[N][N];
visit = new boolean[N][N];
for(int i=0;i<N;i++){
String str = br.readLine();
for(int j=0;j<N;j++){
arr[i][j]=str.charAt(j)-'0';
}
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(!visit[i][j] && arr[i][j]==1){
dfs(i,j);
res.add(cnt);
cnt=0;
}
}
}
sb.append(res.size()+"\n");
Collections.sort(res);
for(int i=0;i<res.size();i++){
sb.append(res.get(i)+"\n");
}
System.out.print(sb);
}
public static void dfs(int x, int y){
visit[x][y]=true;
cnt++;
for(int i=0;i<4;i++){
int nxtx = x+dx[i];
int nxty = y+dy[i];
if(nxtx>=N || nxtx<0 || nxty>=N || nxty<0) continue;
if(arr[nxtx][nxty]==1 && visit[nxtx][nxty]==false)
dfs(nxtx,nxty);
}
}
}
|
cs |
이건 BFS방식으로 풀어본거
2. BFS
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N;
static int[][] arr;
static boolean[][] visit;
static int[] dx = {0,0,-1,1}; //상하좌우
static int[] dy = {1,-1,0,0};
static int cnt=0;
static LinkedList<Integer> res = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
arr = new int[N][N];
visit = new boolean[N][N];
for(int i=0;i<N;i++){
String str = br.readLine();
for(int j=0;j<N;j++){
arr[i][j]=str.charAt(j)-'0';
}
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(!visit[i][j] && arr[i][j]==1){
bfs(i,j);
res.add(cnt);
cnt=0;
}
}
}
Collections.sort(res);
sb.append(res.size()).append("\n");
for(int val : res){
sb.append(val).append("\n");
}
System.out.print(sb);
}
static void bfs(int x, int y){
Queue<Point> q = new LinkedList<>();
q.add(new Point(x,y));
cnt++;
while(!q.isEmpty()){
Point cur = q.poll();
visit[cur.x][cur.y]=true;
for(int i=0;i<4;i++){
int nxtx = cur.x+dx[i];
int nxty = cur.y+dy[i];
if(nxtx<0 || nxtx>=N || nxty<0 || nxty>=N) continue;
if(!visit[nxtx][nxty] && arr[nxtx][nxty]==1) {
q.add(new Point(nxtx, nxty));
visit[nxtx][nxty]=true;
cnt++;
}
}
}
}
}
|
cs |