알고리즘 스터디 6주차 2

2178

• 알고리즘 : 그래프 탐색
• 난이도 : 실버1

문제

2178

접근

• 전형적인 그래프 탐색 문제이다.
• 시작 지점은 무조건 1,1의 위치일 것이다.
• 그래프 탐색하여 가장 짧은 거리를 반환하면 될 것같다.
• 해당 그래프 탐색을 위해 DFS로 이용한다.
  • 칸 수는 100 이하로 DFS로 풀이가 가능 할 것 같다.
• DFS로는 최단 길이를 보장할 수 없다고 한다..

가정

• 보드 판을 세팅한다.
• 해당 보드 판이 1인 경우에만 다음 위치로 이동한다.
• BFS가 최단 경로를 보장한다.

풀어보기

package org.example;

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

public class Main {
	static int N;
	static int M;
	static int[][] board;
	static boolean[][] visited;
	// 이동 방향 (상, 하, 좌, 우)
	private static final int[] dx = {-1, 1, 0, 0};
	private static final int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) throws IOException {

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] first = reader.readLine().split(" ");
		N = Integer.parseInt(first[0]);
		M = Integer.parseInt(first[1]);
		board = new int[N][M];
		visited = new boolean[N][M];
		for(int i = 0; i < N; i++){
			String [] col = reader.readLine().split("");
			for(int j = 0; j < M; j++){
				board[i][j] = Integer.parseInt(col[j]);
			}
		}
		BFS(0,0);
		System.out.println(board[N-1][M-1]);
	}

	public static void BFS(int row, int col){
    //bfs는 큐 사용
		Queue<int[]> queue = new LinkedList<>();
	// 첫번째 값으로 처음 들어온 값을 넣어야한다.
		queue.offer(new int[]{row, col});
        // 방문 기록
		visited[row][col] = true;
        // 큐로 탐색을 시작한다.
		while(!queue.isEmpty()){
        // 큐를 꺼내서 
			int[] cur = queue.poll();
            // 현재 좌표
			int x = cur[0];
			int y = cur[1];
            // 다음 이동 좌표를 구함
			for(int i = 0; i < 4; i++){
            // 다음 이동 좌표 
				int nextRow = x + dx[i];
				int nextCol = y + dy[i];
                // 그래프를 벗어나면 패스
				if(nextCol < 0) continue;
				if(nextRow < 0) continue;
				if(nextRow >= N) continue;
				if(nextCol >= M) continue;
                // 방문했다면 패스
				if(visited[nextRow][nextCol]) continue;
                // board 판의 값이 0 이여도 패스
				if(board[nextRow][nextCol] == 0)continue;
                // 해당 좌표의 이동한 갯수를 구하기 위해 새로운 값으로 갱신하여 찾음 
				board[nextRow][nextCol] = board[x][y] + 1;
                // 방문 기록
				visited[nextRow][nextCol] = true;
                // 다음 좌표가 정상이라면 큐에 담는다. 
				queue.offer(new int[]{nextRow, nextCol});
			}

		}
	}
}

시행착오

• BFS는 어떻게 최단 경로를 보장할까?
  • 가장 가까운 순서부터 탐색 == 가장 낮은 depth부터 탐색
  • Queue는 FIFO로 처리 == 가장 빨리 들어온 노드부터 처리

참고자료