코테 | 강의 - 너비 우선 탐색 - BFS 섹션 - (2)

🟩 4번. 미로의 최단거리 통로 | BFS

• 레벨 탐색 문제이다.
• 출발지점 (0, 0)에서 도착점 (6,6) 까지 갈 건데 갈 때마다 lv++처리하여 dist 배열에 해당 방문한 lv들을 담아가며 처리하면 된다.
• 4방향 탐색할 때 변수 주의해서 사용할 것

package to_0818_2;
//미로의 최단거리 통로 
import java.util.*;
class Solution {
	static int[][] dist;//거리용 
	//4방향 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	public int solution(int[][] board){
		//초기화
		dist = new int[7][7];
		Queue<int[]> Q = new LinkedList<>();
		Q.add(new int[] {0, 0});//시작점 처리
		board[0][0] = 1;//방문체크 
		
		int lv= 0;
		while(!Q.isEmpty()){
			int len = Q.size();
			lv++;
			for(int i=0 ;i<len ;i++) {
				int[] cur = Q.poll();
				for(int j=0; j<4; j++) {
					//여기서 dx인덱스 찍을 때 변수 잘 보고 찍기
					int nx = cur[0] + dx[j];
					int ny = cur[1] + dy[j];
					if(nx < 0 || ny <0 || nx >=7 || ny >=7) continue;
					if(board[nx][ny] == 0) {
						board[nx][ny] = 1;
						Q.add(new int[] {nx, ny});
						dist[nx][ny] = lv;
					}
				}
			}
		}
		if(dist[6][6] > 0) return dist[6][6];
		
		return -1;
	}
	public static void main(String[] args){
		Solution T = new Solution();
		int[][] arr={{0, 0, 0, 0, 0, 0, 0}, 
			{0, 1, 1, 1, 1, 1, 0}, 
			{0, 0, 0, 1, 0, 0, 0}, 
			{1, 1, 0, 1, 0, 1, 1}, 
			{1, 1, 0, 1, 0, 0, 0}, 
			{1, 0, 0, 0, 1, 0, 0}, 
			{1, 0, 1, 0, 0, 0, 0}};
		System.out.println(T.solution(arr));
	}
}

---

🟩 5번. 집을 짓자

풀이

• 각각의 빌딩 1에서 출발하여 모든 빌딩에서 최단거리로 닿는 빈 땅까지의 거리합을 구해야 한다.
• 만약 모든 빌딩 중 하나라도 닿지 않는 빌딩이 있다면 -1 리턴해야 하는 점에 주의
• 체크 배열을 따로 쓰지는 않는다.
• 1인 빌딩값들을 출발점으로 삼기 위해 Q에 담아둘 건데, emptyLand 변수에 처음에는 0으로 초기화하여 board값이 emptyLand변수와 일치할 때만 탐색을 할 것이다. 탐색 완료한 뒤 emptyLand- - 처리
• 이렇게 해야 각각의 출발 빌딩에서 모두가 닿는 빈 땅 0에 대한 탐색이 가능하며, 그 중 누적한 최솟값을 최종 답으로 리턴할 수 있다.

package to_0818_A;
import java.util.*;
class Solution {
	public int solution(int[][] board){
		int answer = 0;
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, 1, 0, -1};
		int n = board.length;
		int[][] dist = new int[n][n];
		Queue<int[]> Q = new LinkedList<>();
		int emptyLand = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(board[i][j] == 1){
					answer = Integer.MAX_VALUE;
					Q.offer(new int[]{i, j});
					int L = 0; 
					while(!Q.isEmpty()){
						L++;
						int len = Q.size();	
						for(int r = 0; r < len; r++){
							int[] cur = Q.poll();
							for(int k = 0; k < 4; k++){
								int nx = cur[0] + dx[k];
								int ny = cur[1] + dy[k];
								if(nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == emptyLand){
									board[nx][ny]--;
									dist[nx][ny] += L;
									Q.offer(new int[]{nx, ny});
									answer = Math.min(answer, dist[nx][ny]);
								}
							}
						}
					}
					emptyLand--;
				}	
			}
		}
		return answer == Integer.MAX_VALUE ? -1 : answer;
	}
		
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[][]{{1, 0, 2, 0, 1}, {0, 0, 0, 0, 0}, {0, 2, 1, 0, 0}, {2, 0, 0, 2, 2}, {0, 0, 0, 0, 0}}));
		System.out.println(T.solution(new int[][]{{1, 0, 0, 1}, {0, 0, 2, 0}, {0, 0, 1, 0}, {2, 2, 0, 0}}));
		System.out.println(T.solution(new int[][]{{1, 2, 0, 0}, {0, 0, 1, 2}, {0, 2, 0, 0}, {0, 2, 1, 0}}));
		System.out.println(T.solution(new int[][]{{1, 0, 0, 1}, {0, 0, 2, 0}, {0, 0, 1, 0}, {2, 2, 0, 1}}));
	}
}

- 다시 풀이 RE

package to_0818_B;
//집을 짓자 - RE 다시 풀기 
import java.util.*;
class Solution {
	public int solution(int[][] board){
		
		int N = board.length;
		int[][]dist = new int[N][N];
		//4방향
		int[] dx = {0, 0, 1, -1};
		int[] dy = {1, -1, 0, 0};
		
		int emptyLand = 0;//최초
		//1) 1인 빌딩 출발점으로 삼기 위해 큐에 담기 
		Queue<int[]> Q = new LinkedList<>();
		for(int i=0; i<N; i++) {
			for(int j =0; j<N; j++) {
				if(board[i][j]==1) {
					Q.offer(new int[] {i, j});
					int lv = 0;
					while(!Q.isEmpty()) {
						lv++; //거리 처리
						int len = Q.size();
						for(int r =0; r<len ; r++) {
							int[] cur = Q.poll();
							for(int k=0; k<4; k++) {
								int nx = cur[0] + dx[k];
								int ny = cur[1] + dy[k];
								if(nx <0 || ny<0 || nx >=N || ny>=N) continue;
								
								if(board[nx][ny]==emptyLand) {
									//닿은 부분은 중복으로 다음에도 닿아야 하기 때문에
									board[nx][ny]--;//처리하고
									Q.add(new int[] {nx, ny});
									dist[nx][ny] += lv;
								}
							}
						}
					}
					emptyLand--;//각 빌딩 1에 대하여 모두 순회하고 중복순회해야하기 때문에 그 기준값도 처리
				}
			}
		}
		int answer = Integer.MAX_VALUE;
		//정답 처리 
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(board[i][j] == emptyLand) {
					answer = Math.min(answer, dist[i][j]);//거기에 누적된 거리합
				}
			}
		}
		return answer == Integer.MAX_VALUE ? -1 : answer;
	}
		
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[][]{{1, 0, 2, 0, 1}, {0, 0, 0, 0, 0}, {0, 2, 1, 0, 0}, {2, 0, 0, 2, 2}, {0, 0, 0, 0, 0}}));
		System.out.println(T.solution(new int[][]{{1, 0, 0, 1}, {0, 0, 2, 0}, {0, 0, 1, 0}, {2, 2, 0, 0}}));
		System.out.println(T.solution(new int[][]{{1, 2, 0, 0}, {0, 0, 1, 2}, {0, 2, 0, 0}, {0, 2, 1, 0}}));
		System.out.println(T.solution(new int[][]{{1, 0, 0, 1}, {0, 0, 2, 0}, {0, 0, 1, 0}, {2, 2, 0, 1}}));
	}
}

---

🟩 6번. 숲속의 기사

풀이

• 결국 2에서 출발해서 4인 산딸기를 거쳐 3인 기사에게 가야하는 최단 시간 구해야 하는 문제이다.
• 처음에 2→4 , 4→ 3으로 BFS 할 생각을 했다
• 그런데 애초에 2와 3 각각에서 못가는 1만 제외하고 탐색하면서 BFS하고 그 값을 서로 +=lv 처리 하면 됐을 문제였다.
• 다시 말해, 2가 출발하여 1 제외한 모든 곳에 닿는 최소거리값에다가,
• 3이 출발하여 1 제외한 모든 곳에 닿는 최소 거리값을 누적하여 더하면 2와 3을 모두 거치는 셈이 되고
• 그 상태에서 애당초 값이 4였던 위치의 dist값들 중 최솟값을 고르면 2, 3, 4를 모두 거치는 최단거리를 찾게 된다.

package to_0818_8;
//숲속의 기사 문제 풀이 - BFS
import java.util.*;
class Solution {
	static int[][] dist;
	static int N, M;
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	//solution
	public int solution(int[][] board){
		int answer = Integer.MAX_VALUE;
		
		N = board.length;
		M = board[0].length;
		
		dist = new int[N][M];
		//2, 3 각각 출발해서 탐색한 거리를 서로 합친 4를 발견하면 그 중 최소값 
		
		Queue<int[]> Q = new LinkedList<>();
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				//출발은 2, 3 각각에서 1 제외한 모든 지점을 탐색하는 식으로 
				if(board[i][j] == 2 || board[i][j] == 3) {
					Q.offer(new int[] {i, j});
					int[][] ch = new int[N][M];//체크용 배열 
					ch[i][j] = 1;
					int lv = 0;
					while(!Q.isEmpty()){
						lv++;
						int len = Q.size();
						for(int r = 0; r<len; r++) {
							int[] cur = Q.poll();
							for(int k =0; k<4; k++) {
								int nx = cur[0] + dx[k];
								int ny = cur[1] + dy[k];
								if(nx <0 || ny< 0 || nx >=N || ny>=M )continue;
								
								if(ch[nx][ny] == 0 && board[nx][ny] != 1) {
									Q.offer(new int[] {nx, ny});
									ch[nx][ny] = 1;
									dist[nx][ny] += lv;//각각 접근하는 모든 레벨에 대하여 누적 처리 
								}
							}
						}
					}
				}
			}
		}
		
		//정답 처리 
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(board[i][j] == 4 && dist[i][j] > 0) {
					answer = Math.min(answer, dist[i][j]);
				}
			}
		}
		return answer;
	}
	//실행 메인 
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[][]{{4, 1, 0, 0, 0, 0, 1, 0},
			{0, 0, 0, 1, 0, 1, 0, 0}, 
			{0, 2, 1, 1, 3, 0, 4, 0},
			{0, 0, 0, 4, 1, 1, 1, 0}}));
		System.out.println(T.solution(new int[][]{{3, 0, 0, 0, 1, 4, 4, 4}, 
			{0, 1, 1, 0, 0, 0, 1, 0}, 
			{0, 1, 4, 0, 1, 0, 0, 0}, 
			{0, 0, 0, 1, 0, 0, 0, 0}, 
			{1, 0, 1, 0, 0, 1, 1, 0}, 
			{4, 0, 0, 0, 1, 0, 0, 0}, 
			{4, 1, 0, 0, 1, 0, 0, 0}, 
			{4, 0, 0, 0, 0, 0, 1, 2}}));
		System.out.println(T.solution(new int[][]{{4, 1, 0, 1, 0}, 
			{0, 1, 0, 1, 0}, 
			{0, 0, 2, 3, 4}, 
			{0, 1, 0, 1, 0}}));
	}
}