[정올] 1113번 119구급대 - 자바(JAVA) / 최소값을 찾아가는 BFS

📑 문제

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=393&sca=99&sfl=wr_subject&stx=119%EA%B5%AC%EA%B8%89%EB%8C%80 

JUNGOL

문제

철수네 동네의 소방서에서는 주민들의 편의를 위해 119 구급 대를 운영하고 있다. 가끔 일어나는 일이지만 위급한 일은 분초를 다투는 일이 많기 때문에 119 구급대가 위급한 일이 발생한 목표지점까지 최대한 빨리 도착해야 한다.

 

119 구급차는 성능이 좋아 일반 자동차보다 아주 빠른 속도로 주행할 수 있지만 코너를 돌 때에는 일반 자동차처럼 속도를 완전히 줄여야 하기 때문에 목표지점에 도달할 때 까지 되도록 코너를 돌지 않고 직선 도로를 통해 도착해야 시간을 줄일 수 있다.

 

 

 

위의 테이블은 119 구급 대에서 위급한 일이 발생하는 목표지점까지의 지도를 표시한 것이다. 흰색으로 표시되어 있는 부분이 차가 지나갈 수 있는 길을 나타내고 회색으로 칠해져 있는 곳이 장애물을 의미한다. 이제 소방서에서 위급한 일이 발생한 목표지점까지 가장 빠른 시간에 도착할 수 있는 경로를 찾아보자. (출발점은 항상 왼쪽 맨 위(0,0)이고 도착점은 좌표로 주어진다. 119 구급차는 가로와 세로 방향으로만 움직일 수 있고 대각선으로는 움직일 수 없다.)

 

입력형식

첫째 줄에 지도의 크기 M(1≤M≤100)×N(1≤N≤100)이 주어진다. 두 번째 줄에는 목표점 m,n이 주어진다. (단 M=m+1, N=n+1) 다음 N줄에는 M개의 값이 주어지며 각 값에서 1은 도로이고 0은 진입할 수 없는 물건이 놓여 있다.

 

출력형식

첫째 줄에 최소 코너를 도는 횟수를 출력한다.

 

 

 

 

 

 

 

 

 

✒️ 풀이

 

 1. 시작 위치부터 BFS 탐색을 시도한다.

 

 2. 전체 위치의 경로까지 오는데 돈 코너의 횟수를 저장하는 배열을 선언한다.

    특정 위치를 조회할 때마다, 현재 위치의 코너 횟수보다 적은 곳인지 큰 곳인지 확인한다.

    코너 횟수가 현재 위치보다 적은 곳만 방문한다.

 

 3. 코너인지 확인하는 방법은 현재 위치의 방향 인덱스와 비교하는 것이다.

    왼쪽 칸에서 오른쪽으로 이동해서 현재 위치로 왔다면, 현재 위치에서 오른쪽에 있는 좌표만이 직진일 것이다.

    뒤로 돌아가는 경우는 코너 횟수가 현재와 같거나 그보다 크므로 무시된다.

    따라서 위치를 큐에 넣을 때마다, 어떤 방향에서 왔는지 알려주는 방향 인덱스를 함께 넣어준다.

 

 4. 목표 위치가 나타나면 목표 값과 비교하여 더 작은 값으로 업데이트 해준다.

    목표 위치에 도달했다고 바로 코너 값을 리턴하면 안되는 이유는 아래와 같은 경우가 있기 때문이다.

 

    만약 (0,0)에서 주변탐색을 할 때 하보다 우방향에 먼저 접근한다면,

    (0,0)시작 -> 우 -> 하 -> 우: 코너 돈 횟수 2번

    (0,0)시작 -> 하 -> 우 -> 우: 코너 돈 횟수 1번

    와 같이 처리되기 때문에, 먼저 도착했음에도 코너를 돈 횟수가 더 많을 수 있다.

 

0	0	X
0	1	2

 

 

 

 

 

 

🙋‍♀️ 의견

 BFS는 몇 번을 하긴 했지만 가끔 멘붕에 빠지는 순간이 오는 것 같다.

 오늘은 visited 배열을 선언을 해야 하는지 멘붕에 빠졌다.

 이미 방문한 위치라도 최소값이 갱신되면 어쩌지?했는데 생각해보니 '코너' 도는 횟수를 따지기 때문에 한 번이라도 더 돈 경로는 덜 돈 경로보다 특정 위치에 늦게 도착할 수 밖에 없다. 즉, 처음 방문한게 가장 코너를 돈 횟수가 적은 것이 되기 때문에 visited를 써도 최소값을 찾아낼 수 있다.

 visited를 쓴 코드는 지영님 것을 가져왔다. 지영님도 코드를 이해하기 쉽게 정말 잘 짜시는 듯 하다.

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

public class Main_정올_1113_119구급대 {

	// BFS. 대기열에 위치값과 corner값(현재 방향*(1, -1)과 같지 않으면 증가) 함께 전달
	// 이미 방문한 배열이라면 코너값이 더 작을 때 재진입
	static int M, N, m, n;
	static int[][] map, val;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());	//가로
		N = Integer.parseInt(st.nextToken());	//세로
		st = new StringTokenizer(br.readLine());
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		map = new int[M][N];
		val = new int[M][N];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				val[i][j] = 1000;
			}
		}//input
		System.out.println(bfs());
	}//end of main
	
	private static int bfs() {
		int[] dr = {1,-1,0,0};
		int[] dc = {0,0,1,-1};
		
		int result = Integer.MAX_VALUE;
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] {0,0,0,-1});	//r,c,cnt,dir
		val[0][0] = 0;
		
		while(queue.size()>0) {
			int[] cur = queue.poll();
			int r = cur[0];
			int c = cur[1];
			int cnt = cur[2];
			int dir = cur[3];
			
			if(r==m && c==n) {
				result = Math.min(result, cnt);
				continue;
			}
			
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				int ncnt = cnt;
				
				if(nr<0||nc<0||nr>=M||nc>=N||map[nr][nc]==0||
						val[nr][nc]<=cnt) continue;
				if(dir!=-1) {					
					if(dir!=i) ncnt++;
				}
				val[nr][nc] = ncnt;
				queue.offer(new int[] {nr,nc,ncnt,i});
			}
		}
		return result;
	}//bfs
}//end of class

 

 

 

💻 다른사람 소스코드: 자바(Java)

public class Main_1113_119구급대 {

	// 최소 코너를 도는 횟수
	// bfs돌면서 코너도는 횟수 저장 - 완탐.. 최소횟수가 저장되면 최소보다 큰경우 탈락

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

		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());

		char[][] map = new char[m][n];
		boolean[][] visited = new boolean[m][n];

		st = new StringTokenizer(br.readLine(), " ");
		int endX = Integer.parseInt(st.nextToken());
		int endY = Integer.parseInt(st.nextToken());

		for (int i = 0; i < n; i++) {
			String input = br.readLine();
			for (int j = 0; j < m; j++) {
				map[i][j] = input.charAt(j << 1);
			}
		}

		int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
		// 상0 하1 좌2 우3
		Queue<int[]> q = new LinkedList<int[]>();

		if (map[0][1] == '1')
			q.add(new int[] { 0, 1, 3, 0 }); // r c d cnt
		if (map[1][0] == '1')
			q.add(new int[] { 1, 0, 1, 0 });
		visited[0][0] = true;

		int min = 987654321;
		while (q.size() > 0) {
			int[] cur = q.poll();
			int cnt = cur[3];

			visited[cur[0]][cur[1]] = true;

			if (cur[0] == endX && cur[1] == endY) {
				if (min > cnt)
					min = cnt;
				continue;
			}

			for (int i = 0; i < 4; i++) {
				int nr = cur[0] + dir[i][0];
				int nc = cur[1] + dir[i][1];

				if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc] || map[nr][nc] == '0')
					continue;

				if (i == cur[2])
					q.add(new int[] { nr, nc, i, cnt });
				else if (cnt + 1 < min)
					q.add(new int[] { nr, nc, i, cnt + 1 });
			}
		}
		System.out.println(min);
	}
}

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨