글 읽기 - DFS가 안돌아가는데, 이유를 모르겠습니다(범위 부분, 디버깅 캡쳐부분 있음)

eodhlwjr97 1년 전 0

안녕하세요

2583번 영역구하기 문제를 DFS를 사용해서 풀었습니다.

행과 열로 보기 위해서,

INPUT 을 오른쪽으로 90도 회전한 형태로 풀었고, 두번째 사진과 같습니다(색칠한 부분을 1로 두고 풀었습니다.)

preview

preview

(arr 디버깅시 input을 오른쪽으로 90도 회전한 형태로 잘 나옵니다.)

arr 잘 저장하고, 색칠부위도 잘 저장되어있고 위에는 문제 없는 것 같습니다.

근데, DFS가 안돌아가길래

System.out.println("여기까지 도착"); 이라는 문장 넣고 한줄 한줄 디버깅을 해보았는데,

89line에 이 문장을 넣었을 때 <여기까지도착> 이라는 문장이 콘솔에 출력되는데

다음 사진과 같이 범위 체크 부분에서 모든 경우가 다 범위체크 if문 안으로 들어가버려서, dfs 재귀 자체를 타지 못하고 있는 상태입니다. (범위를 넘어가지 않는 부분조차도 저기 if문에서 걸려버립니다. 콘솔창에서 모든 경우가 "여기서 다걸림"을 출력합니다. 일부 캡처만 올립니다.)

제가 잘못 생각한 부분이 어디일까요? 답답해서 죽을것같아요....

preview

preview

import java.io.*;
import java.util.*;

public class Main {
	static int R, C, K;
	static int[][] arr;
	static boolean[][] isVisited;
	static int[][] pos;
	static int width, height;

	static int[] dr = { 0, 0, 1, -1 };
	static int[] dc = { 1, -1, 0, 0 };

	static StringBuilder sb = new StringBuilder();

	static ArrayList<Integer> list;
	static int cnt;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		int C = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		arr = new int[R][C];
		isVisited = new boolean[R][C];
		pos = new int[K + 1][4]; // [n번째사각형][좌표]

		width = 0;
		height = 0;
		// 색칠하기
		for (int i = 1; i <= K; i++) {
			st = new StringTokenizer(br.readLine());
			pos[i][0] = Integer.parseInt(st.nextToken()); // 사각형 왼쪽 꼭지점 r좌표
			pos[i][1] = Integer.parseInt(st.nextToken()); // 사각형 왼쪽 꼭지점 c좌표
			pos[i][2] = Integer.parseInt(st.nextToken()); // 사각형 오른쪽 꼭지점 r좌표
			pos[i][3] = Integer.parseInt(st.nextToken()); // 사각형 오른쪽 꼭지점 c좌표

			width = pos[i][3] - pos[i][1]; // 2
			height = pos[i][2] - pos[i][0]; // 4
			int startPointR = pos[i][0];
			int startPointC = pos[i][1];
			for (int r = startPointR; r < startPointR + height; r++) {
				for (int c = startPointC; c < startPointC + width; c++) {
					// 이미 색칠한 부위(1)라면 건너 뛰기
					if (arr[r][c] == 1)
						continue;
					arr[r][c] = 1;
				}
			}
		}

		// debug
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}

		list = new ArrayList<>();
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (arr[i][j] == 0 && !isVisited[i][j]) {
					cnt = 0; // 덩어리 세는 변수
					dfs(i, j);
					list.add(cnt);
				}
			}
		}
		
		Collections.sort(list);
		System.out.println(list.size());
		for (Integer area : list) {
			System.out.print(area + " ");
		}
	}

	private static void dfs(int r, int c) {
		isVisited[r][c] = true;
		cnt++;

		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			
			// 범위초과하면 리턴
			if (nr < 0 || nr >= R || nc < 0 || nc >= C)
				continue;
			
			if (arr[nr][nc] == 0 && !isVisited[nr][nc]) {
				dfs(nr, nc);
			}

		}

	}

}

댓글을 작성하려면 로그인해야 합니다.