TIL

그래프 관련 문제를 2문제 풀었다.
둘 다 DFS로 풀었다.

백준 2667번: 단지번호붙이기

https://www.acmicpc.net/problem/2667

나는 좌표 관련 문제만 나오면 지레 겁을 먹고만다.
인접한 좌표를 확인하며 푸는 방법을 이번에 알게되었다.

1. 한칸 씩 이동 시키기 위해 int 배열을 세운다

 static int[] dx = { -1, 1, 0, 0 };
 static int[] dy = { 0, 0, -1, 1 };

2. 반복문을 4번씩 돌면서 좌표에 dx와 dy를 하나씩 더한다.

for(int i=0;i<4;i++) {
    int nx= x+dx[i];
	int ny= y+dy[i];

3. 좌표의 처음이나 끝일 때 이동시키면 오류가 나니 조건을 세운다.

if(nx>=0 && ny>=0 && nx<M &&ny<N) {
    //실행문
}

이제 문제를 풀어보면
1. 그림 1을 2차원 배열로 구현한다.
2. 그림 1과 같은 크기의 boolean 배열을 만든다. 이것은 탐색 할때 정점을 방문했는지 체크하는 용도다.
3. 탐색을 한다. DFS/ BFS 어느 것이든 좋다.
4. 탐색하면서 방문한 count를 센다. 이를 ArrayList 에 넣는다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	
	static int N;
	static int[][] map;
	static int count;
	static boolean[][] visited;
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	
	static ArrayList<Integer> result;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N=Integer.parseInt(br.readLine());
		map= new int[N][N];
		visited= new boolean[N][N];
		for(int i=0;i<N;i++) {
			String s= br.readLine();
			for(int j=0;j<N;j++) {
				map[i][j]=s.charAt(j)-'0';
			}
		}
		
		count=0;
		result=new ArrayList<Integer>();
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(map[i][j]==1&&!visited[i][j]) {
					count=1;
					Search(i,j);
					result.add(count);
				}
			}
		}
		Collections.sort(result);
		bw.write(result.size()+"\n");
		for(int i=0;i<result.size();i++) {
			bw.write(result.get(i)+"\n");
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
    
	public static int Search(int x,int y) {
		visited[x][y]=true;
		
		for(int i=0;i<4;i++) {
			int nx=x+dr[i]; //x로 한 칸 이동
			int ny=y+dc[i]; //y로 한 칸 이동
			
			if(nx>=0 && ny>=0 && nx<N &&ny<N) {
				if(map[nx][ny]==1&&!visited[nx][ny]) {
					Search(nx,ny);
					count++;
				}
			}
		}
		return count;
	}
}

백준 1012번: 유기농 배추

https://www.acmicpc.net/problem/1012
2667번과 아주 유사하다.
배추 밭 2차원 배열을 만든 후 배추가 있는 부분만 1로 표시한다.
그리고 탐색을 수행 후 count를 높이고 count값을 출력하면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int[][] map;
	static int count = 0;
	static ArrayList<Integer> result;
	static int T, M, N, K;
	static boolean[][] visited;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		T = Integer.parseInt(br.readLine());
		for (int i = 0; i < T; i++) {
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			map = new int[M][N];
			visited=new boolean[M][N];
			
			
			for (int k = 0; k < K; k++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());

				map[a][b] = 1;
			}
			count=0;

			for (int a = 0; a < M; a++) {
				for (int b = 0; b < N; b++) {
					if (map[a][b] == 1 && !visited[a][b]) {
						
						Search(a, b);

						count++;
					}
				}
			}
			
			bw.write(String.valueOf(count)+"\n");
			
		}
		bw.flush();
		bw.close();
	}

	public static void Search(int x, int y) {
		visited[x][y]=true;
		
		for(int i=0;i<4;i++) {
			int nx= x+dx[i];
			int ny= y+dy[i];
			
			if(nx>=0 && ny>=0 && nx<M &&ny<N) {
				if(map[nx][ny]==1&&!visited[nx][ny]) {
					Search(nx,ny);

				}
			}
		}
		
	}

}