개발생각

[Baekjoon] [https://www.acmicpc.net/problem/1012]

기본적인 그래프 문제

풀이 )

1. 이중 포문에서 배추의 위치를 찾는다. 또한 현재 방문하지 않은 배추의 위치여야한다.

2. 찾은 배추의 위치에서 인접한 배추의 위치를 계속 찾는다. 또한 방문하지 않은 인접 위치여야한다. ( ←↑→↓ : 순서 xx = [-1,0,1,0] yy = [0,-1,0,1] ) // 이를 재귀탐색 DFS

3. 배추가 인접하지 않거나 이미 방문한 지역이면 getDFS 함수를 빠져나온다.

4. 이중포문으로 돌아와서 다시 배추의 위치를 찾는다

5. 1~4 반복.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int m; //가로
	static int n; //세로
	static int k; //배추의 개수
	static int[][] land;
	static int[][] visit;
	static int[] xx = {-1, 0, 1, 0};
	static int[] yy = {0, -1, 0, 1};


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> answer = new ArrayList<>();
		int tc = sc.nextInt();

		while(tc>0){
			m = sc.nextInt();
			n = sc.nextInt();
			k = sc.nextInt();

			land = new int[m][n];
			visit = new int[m][n];
			int worms = 0;

			for(int i=0;i<k;i++){
				int x = sc.nextInt();
				int y = sc.nextInt();
				//배추의 좌표 x,y
				land[x][y] = 1;
			}

			for(int i=0;i<m;i++){
				for(int j=0;j<n;j++){
					if(land[i][j] == 1 && visit[i][j] == 0){
						getDFS(i, j);
						worms++;
					}
				}
			}

			answer.add(worms);
			tc--;
		}

		

		for(int i=0;i<answer.size();i++){
			System.out.println(answer.get(i));
		}
	}

	public static void getDFS(int x, int y){
		visit[x][y] = 1;

		for(int i=0;i<4;i++){
			int ax = x+xx[i];
			int ay = y+yy[i];

			if(ax>=0 && ax<m && ay>=0 && ay<n){
				if(land[ax][ay] == 1 && visit[ax][ay] == 0){
					getDFS(ax, ay);
				}
			}
		}
	}
}

기본적인 그래프 문제, DFS 접근

풀이)

지도에서 현재 섬인 경우 해당 섬의 (위, 아래, 오른쪽, 왼쪽, 그리고 대각선 4방향) 확인. 

getDFS(x, y);

if) 해당 방향으로 섬인 경우 재귀탐색으로 다시 확인. // 단, 아직 방문하지 않은 섬인 경우

else) 바다인 경우 return.

--> 함수 return 경우 모든 인접 지역을 방문했거나 바다인경우로 섬+1

map[][] : 배열로 섬과 지도를 나타내는 지도 저장

visit[][] : 이미 방문한 지역 저장 // 1 : 방문, 0 : 미방문

DFS 그래프로 <위, 아래, 오른쪽, 왼쪽, 그리고 대각선 4 방향> 이동

  int[] xx = {-1, 0, 1, 1, 1, 0, -1, -1};

int[] yy = {-1, -1, -1, 0, 1, 1, 1, 0};

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int w;
	static int h;
	static int[][] map;
	static int[][] visit;
	static int[] xx = {-1, 0, 1, 1, 1, 0, -1, -1};
	static int[] yy = {-1, -1, -1, 0, 1, 1, 1, 0};
	
	static ArrayList ar = new ArrayList<>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			w = sc.nextInt();
			h = sc.nextInt();
			
			if(w == 0 && h == 0){
				break;
			}
			
			map = new int[w][h];
			visit = new int[w][h];
			int landCount =0;
			
			for(int i=0;i<h;i++){
				for(int j=0;j<w;j++){
					map[j][i] = sc.nextInt();
				}
			}
			
			for(int i=0;i<w;i++){
				for(int j=0;j<h;j++){
					if(map[i][j] == 1 && visit[i][j] == 0){
						getDFS(i, j);
						landCount++;
					}
				}
			}
			ar.add(landCount);
		}
		
		for(int i=0;i<ar.size();i++)
			System.out.println(ar.get(i));
	}
	
	public static void getDFS(int x, int y){
		visit[x][y] = 1;
		
		for(int i=0;i<8;i++){
			int ax = x+xx[i];
			int ay = y+yy[i];
			if(ax>=0 && ax<w && ay>=0 && ay<h){
				if(map[ax][ay] == 1 && visit[ax][ay] == 0){
					getDFS(ax, ay);
				}
			}
		}
	}
}