백준 2178번 : 미로 탐색

문제 풀이

• 접근법 : BFS
  한 좌표로부터 인접한 좌표를 하나씩 방문해가면서 각 좌표의 최단거리를 구해낸다.

• 풀이 과정

  1. (1,1) 좌표를 큐에 삽입하고 최단거리로 0을 저장한다.
  2. 큐의 첫번째 원소를 꺼내고, 인접한 4개의 좌표에 대해 우상좌하 순으로 '3번' 작업을 수행한다.
  3. 해당 좌표가 갈 수 있는 경로이고, 아직 방문하지 않았으면(최단거리==0인 경우) 해당 좌표의 최단거리를 dequeue한 좌표의 최단거리 + 1로 저장하고 해당 좌표를 enqueue한다.
  4. '2번'부터 '3번'까지의 작업을 큐가 빌 때까지 반복한다.

java 구현 코드

package ch08_BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class p2178 {

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

		int n = Integer.valueOf(st.nextToken());  // 세로 길이 n
		int m = Integer.valueOf(st.nextToken());  // 가로 길이 m 
	
		char[][] mazeArr = new char[n + 2][m + 2];  // 미로를 저장할 배열
		
		// 미로 배열 세팅하기
		for (int i = 0; i < n; i++) { 
			String input = br.readLine();
			
			for (int j = 0; j < m; j++) {
				mazeArr[i + 1][j + 1] = input.charAt(j);
			}
		}
		
		int[] dx = {1, 0, -1, 0};  // 우상좌하
		int[] dy = {0, 1, 0, -1};
		
		// BFS 
		Queue<Point> queue = new LinkedList<>();  // 큐 생성
		int[][] distance = new int[n + 2][m + 2];  // 각 좌표에서 (1,1)까지 최단거리 저장 배열
		
		distance[1][1] = 0;  // (0,0)의 최단거리 값 0으로 세팅 (생략 가능)
		queue.add(new Point(1, 1));  // (1,1) 좌표 enqueue
		
		while(!queue.isEmpty()) {  // queue가 빌 때까지 반복
			Point tmp = queue.remove();  // dequeue
			
			int tmpX = tmp.X;
			int tmpY = tmp.Y;
			
			int tmpDistance = distance[tmpX][tmpY];
			
			for (int i = 0; i < 4; i++) {  // 꺼낸 좌표의 우상좌하 순으로 탐색
				int dX = tmpX + dx[i];
				int dY = tmpY + dy[i];
				
				if (mazeArr[dX][dY] == '1' && distance[dX][dY] == 0) {  // 갈 수 있는 경로인데 아직 방문 안 했으면 
					distance[dX][dY] = tmpDistance + 1;  // dequeue한 좌표의 최단거리에 1 더하기
					queue.add(new Point(dX, dY));  // enqueue
				}
			}
		}

		System.out.println(distance[n][m] + 1);
		
	}

}

class Point {
	int X;
	int Y;
	
	Point(int X, int Y) {
		this.X = X;
		this.Y = Y;
	}
}

comment

풀이 날짜 : 2023/12/22 (금)

내년에 코딩테스트 응시하려면 12월에 남은 며칠동안 알고리즘 공부 진도를 빨리 나가야 하는데....자꾸 공부에 집중이 잘 안 된다. 아무래도 도파민 중독으로 한 곳에 집중을 제대로 못하는 것 같다.
오늘 오전은 집에서 뒹굴거리느라 시간을 낭비했지만 오후에 뒤늦게라도 정석에 온 내 자신에게 칭찬해주자 👏

일단 오늘 하루에 후회 없도록, 핸드폰 끄고 11시까지 열심히 달려야겠다.