백준 알고리즘 - 1012_배추

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

문제 설명
배추가 심어져 있는 공간이 1, 아무것도 없는 공간이 0으로 표시된다.
이 문제는 서로 인접해 있는 '1'이 몇 덩어리(?)인지 세는 문제이다.

문제 풀이
처음에는 '서로 인접해 있는' 1을 찾는게 아니라 모든 1을 찾는 코드를 짰다...ㅎㅎㅎ
한 번 '1'을 찾으면 어떻게 인접해있는 '1'만 다 찾고 빠져나와서 count해줘야 할 지 몰랐었다. 이것저것 다 시도해봤으나 삽질만 했다.ㅠ


그래서 예전에 풀었던 정답을 참고해 풀었다.

먼저 main 메소드에서 입력된 테스트케이스 수만큼 입력을 받는다.

public static void main(String[] args) {
	int testCase = sc.nextInt();
	for(int t = 0; t < testCase; t++) {
		input();
	}
}

그 다음, 모든 좌표를 돌며 '한 번도 방문하지 않았고', '배추가 심어져 있을 때만' count를 세고, 재귀함수를 호출한다.
이렇게 하면 배추가 심어져 있는 부분만 탐색하다 빠져나올 수 있고, 모든 '1'을 세지 않을 수 있다.

for(int i = 0; i < x; i++) {
	for(int j = 0; j < y; j++) {
		if(check[i][j] == false && map[i][j] == 1) {
			answer++;
			solution(i, j, map, check);
		}
	}
}

일단 solution 함수를 호출하게 되면, 가장 먼저 해당 좌표에 대한 방문기록을 찍고, 사방을 탐색하기 위한 dx, dy 값 설정을 한다.

check[x][y] = true;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

그 다음, for문으로 상하좌우 네 방향을 탐색한다.
nx, ny는 다음으로 탐색할 좌표이다.

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

현재 위치인 x와 y에 방향을 정해주는 dx, dy를 더해줌으로써 다음 방향을 정하는 것이다.

그리고 다음으로 나아갈 좌표값이 '1'이고, 아직 한 번도 방문하지 않아야 하며, 정해진 좌표값을 벗어나지 않았으면 다시 재귀함수를 호출한다.

나는 처음에 재귀함수를 호출할 때 조건문을 아래와 같이 작성했는데,
만약 x, y가 (0, 0) 이면 nx, ny에 -1값이 들어가게 되기 때문에 이렇게 코드를 짜면 indexOutOfBounce -1 어쩌고 하는 배열초과 에러가 생기게 된다.

if(map[nx][ny] == 1 && check[nx][ny] == false && isArrange(nx,ny)) {

isArrange 함수를 조건문 맨 처음에 써서 nx, ny 값이 범위 내를 벗어나진 않는지 체크해줘야 한다.

if(isArrange(nx,ny) && map[nx][ny] == 1 && check[nx][ny] == false) {
	solution(nx, ny, map, check);
}

또, 나는 if문 뒤에 else if 로 좌표값이 '0'이면 break를 써서 for문을 나가게 했는데, 이렇게 하면 다른 결과값이 나오게 된다ㅠ

else if(isArrange(nx,ny) && map[nx][ny] == 0 && check[nx][ny] == false) {
	break;
}

아마 네 방향으로 탐색 중에 '0'이 있게 되면 더 탐색을 안하고 도중에 빠져나오게 돼서 그런 것 같다ㅠㅠ

이렇게 탐색을 끝내고 다시 main으로 오게 되면, 정답을 출력하고 반드시 초기화 해줘야 한다.

System.out.println(answer);
answer = 0;

왜냐하면 테스트케이스 수대로 각 케이스마다 계산해서 정답을 출력하는 식이기 때문이다.

전체 코드

public class Practice2 {
	static Scanner sc = new Scanner(System.in);
	static int x, y;
	static int answer;
	public static void main(String[] args) {
		int testCase = sc.nextInt();
		
		for(int t = 0; t < testCase; t++) {
			input();
		}
	}

	private static void input() {
		// TODO Auto-generated method stub
		//가로,세로,배추위치 개수
		x = sc.nextInt();
		y = sc.nextInt();
		int numberOfCabbage = sc.nextInt();
		
		//맵, check 초기화(init)
		int[][] map = new int[x][y];
		boolean[][] check = new boolean[x][y];
		for(int ix = 0; ix < x; ix++) {
			for(int iy = 0; iy < y; iy++) {
				map[ix][iy] = 0;
				check[ix][iy] = false;
			}
		}
		
		//배추위치 개수만큼 반복문으로 입력받음
		for(int c = 0; c < numberOfCabbage; c++) {
			int mx = sc.nextInt();
			int my = sc.nextInt();
			map[mx][my] = 1;
		}
		
		//System.out.println();
		
		//test용 출력
		/*
		for(int t1 = 0; t1 < x; t1++) {
			for(int t2 = 0; t2 < y; t2++) {
				System.out.print(map[t1][t2]+" ");
			}
			//System.out.println();
		}*/
		
		for(int i = 0; i < x; i++) {
			for(int j = 0; j < y; j++) {
				if(check[i][j] == false && map[i][j] == 1) {
					answer++;
					solution(i, j, map, check);
				}
			}
		}
		
		System.out.println(answer);
		answer = 0; //answer 초기화 필수
	}


	private static void solution(int x, int y, int[][] map, boolean[][] check) {
		//상하좌우
		int dx[] = {-1,1,0,0};
		int dy[] = {0,0,-1,1};
		int nx, ny;
	
		//방문기록 찍기
		check[x][y] = true;
		
		//상하좌우 "탐색"
		for(int d = 0; d < 4; d++) {
			nx = x + dx[d];
			ny = y + dy[d];
			
			/*
				이렇게 isArrange를 "map[nx][ny]"보다 늦게 써주면, 이미 "indexOutOfBounce -1"가 생기고 나므로
				반드시 isArrange를 맨 앞에 선언해준다!!!
			*/
			//if(map[nx][ny] == 1 && check[nx][ny] == false && isArrange(nx,ny)) {
			if(isArrange(nx,ny) && map[nx][ny] == 1 && check[nx][ny] == false) {
				solution(nx, ny, map, check);
				//System.out.println(nx+", "+ny+", "+map[nx][ny]+" >> "+answer);
			//}else if(map[nx][ny] == 0 && check[nx][ny] == false && isArrange(nx,ny)) {
			}/*else if(isArrange(nx,ny) && map[nx][ny] == 0 && check[nx][ny] == false) {
				break;
			}*/ //왜 이 부분이 있으면 답이 다르지 ..? //아 4방향으로 탐색 중 0이 있으면 탐색을 하다말게돼서 그런가
			
		}
	}

	private static boolean isArrange(int nx, int ny) {
		return nx < x && ny < y && nx >= 0 && ny >= 0; 
	}

}

Git gist 주소
https://gist.github.com/ysyS2ysy/6f925618b7b2d9dea55ba5b01a8fa2d0