[백준] 2178번, 2667번

격자, 좌표, 경로 탐색 문제 -> BFS(너비우선탐색), DFS(깊이우선검색) 사용

 

2178번 - 미로 탐색

<문제>

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

2178번: 미로 탐색

 

<문제 풀이>

최근 최단거리 문제를 풀 때, 역추적 방법을 사용하여 문제를 해결했던 적이 있어 역추적 방법으로 문제 접근을 했습니다. 

하지만 생각해 보니 역추적으로 풀었던 문제는 오른쪽 방향을 우선순위로 이동한다는 조건이 있었습니다. 2178번 문제는 방향 우선순위 없이 칸의 숫자가 1인 칸은 모두 이동이 가능한 문제이기 때문에 역추적 방법은 적합하지 않다고 판단했습니다. 

구글링의 도움을 받아 현재 위치에서 상하좌우의 이동 경우의 수(범위에 부합하는)를 모두 탐색하는 방법을 사용하여 문제를 해결하였습니다. 

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

상하좌우의 칸을 모두 살피기 위해 위의 배열이 필요했습니다. 

public static boolean range_Chk() { //index 범위 확인 
	return (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M);
}

또한, 상하좌우로 이동했을 때 해당 칸이 범위 내에 존재하는 칸인지 확인하기 위해 위의 메서드를 사용했습니다. 

 

<코드>

핵심 코드 

while(!queue.isEmpty()) {
	int tmp[] = queue.poll(); //현재 위치
	int tx = tmp[0];
	int ty = tmp[1];
			
	for(int i = 0; i < 4; i++) { //상 하 좌 우 모두 탐색
		//nextX, nextY -> 현재 위치를 의미함
		nextX = tx + dx[i]; 
		nextY = ty + dy[i];
				
		if(range_Chk() && path[nextX][nextY] == 1 && !visit[nextX][nextY]) {
			queue.add(new int[] {nextX, nextY});
			path[nextX][nextY] = path[tx][ty] + 1; 
			//어차피 1이라는 가정하에 여기까지 넘어오기 때문에 해당 요소에 1만 더해주면 이동 칸 수를 알 수 있음
			visit[nextX][nextY] = true;
		}
	}
}

 

전체 코드

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

public class Main {
	static final int MAX = 100;
	static int N, M;
	static int nextX, nextY;
	static int MIN = Integer.MAX_VALUE;
	static int[][] path;
	static boolean[][] visit;
	
	//상 하 좌 우
	static int dx[] = {-1, 1, 0, 0};
	static int dy[] = {0, 0, -1, 1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		path = new int[N][M];
		visit = new boolean[N][M]; 
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < M; j++) {
				path[i][j] = Character.getNumericValue(str.charAt(j)); 
			}
		}
		
		visit[0][0] = true; //(0, 0)이 시작점이 됨
		bfs(0, 0);
		System.out.println(path[N-1][M-1]); //도착지점
	}
	
	public static void bfs(int row, int col) {
		Queue<int[]> queue = new LinkedList<>(); //[row, col] 형태를 저장
		queue.add(new int[] {row, col});
		
		while(!queue.isEmpty()) {
			int tmp[] = queue.poll(); //현재 위치
			int tx = tmp[0];
			int ty = tmp[1];
			
			for(int i = 0; i < 4; i++) { //상 하 좌 우 모두 탐색
				//nextX, nextY -> 현재 위치를 의미함
				nextX = tx + dx[i]; 
				nextY = ty + dy[i];
				
				if(range_Chk() && path[nextX][nextY] == 1 && !visit[nextX][nextY]) {
					queue.add(new int[] {nextX, nextY});
					path[nextX][nextY] = path[tx][ty] + 1; 
					//어차피 1이라는 가정하에 여기까지 넘어오기 때문에 해당 요소에 1만 더해주면 이동 칸 수를 알 수 있음
					visit[nextX][nextY] = true;
				}
			}
		}
	}
	
	public static boolean range_Chk() { //index 범위 확인 
		return (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M);
	}
}

 

<결과>

 

 

---

2667번 - 단지번호 붙이기 

<문제>

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

2667번: 단지번호붙이기

 

<문제 풀이>

이 문제도 2178번 문제와 유사하게 미로를 탐색하는 문제이기 때문에 상하좌우 칸의 숫자가 0인지 1인지 확인하는 방법으로 문제를 풀었습니다. 

현재 위치한 칸의 숫자가 1일 때만 dfs 메서드를 호출하여 단지 개수(cnt)와 단지 번호(num)를 체크하여 단지 개수를 list에 저장하였습니다.

 탐색이 끝난 뒤 단지 개수를 먼저 출력하고, list를 오름차순으로 정렬한 뒤 출력하여 문제를 마무리하였습니다. 

 

<코드>

전체 코드

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

public class Main {
	static int N;
	static int[][] arr;
	static boolean[][] visit;
	static int dx[] = {-1, 1, 0, 0};
	static int dy[] = {0, 0, -1, 1};
	
	static int cnt = 0, num = 0;
	static int nx = 0, ny = 0;
	static List<Integer> list = new ArrayList<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		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] = Character.getNumericValue(str.charAt(j));
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(arr[i][j] == 1 && !visit[i][j]) {
					cnt = 0; //단지 개수 초기화
					num++; //단지 번호 1증가
					dfs(i, j);
					
					list.add(cnt); //결과 저장
				}
			}
		}
		
		Collections.sort(list); //오름차순 정렬
		System.out.println(num);
		
		for(int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
	}
	
	public static void dfs(int row, int col) {
		visit[row][col] = true;
		arr[row][col] = num; //단지 번호를 대입
		cnt++; //단지 개수 증가 
		
		for(int i = 0; i < 4; i++) { //상하좌우 살피기 
			nx = dx[i] + row;
			ny = dy[i] + col;
			
			if(range_Chk() && arr[nx][ny] == 1 && !visit[nx][ny]) {
				visit[nx][ny] = true;
				arr[nx][ny] = num;
				dfs(nx, ny);
			}
		}
	}
	
	public static boolean range_Chk() { //index 범위 확인 
		return (nx >= 0 && nx < N && ny >= 0 && ny < N);
	}
}

 

<결과>

 

 

 

2023.02.12