[백준/java] 2178번: 미로 탐색 - BFS

2178번: 미로 탐색

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

2178번: 미로 탐색

728x90

2178번: 미로 탐색

이 문제에서는 고려해야할 것이

현재 노드가 방문한 노드인지 확인하는 로직이 필요하고,

또 현재 노드의 좌표가 도착점 좌표와 같을 때 BFS 탐색을 종료하고 찾은 개수를 출력하면 된다.

 

if(visit[cur.y][cur.x]) continue;
visit[cur.y][cur.x] = true;
			
if(cur.y == N -1 && cur.x == M - 1) {
	cnt = cur.step;
	return;
}

 

반응형

 

아래는 완성된 소스코드이다.

package 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 MazeSearch {
	static int[] dy = {1, 0, -1, 0};
	static int[] dx = {0, 1, 0, -1};
	static int[][] map;
	static boolean[][] visit;
	static int N, M, cnt;
	static class Node {
		int y, x, step;
		public Node(int y, int x, int step) {
			this.y = y;
			this.x = x;
			this.step = step;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		
		map = new int[N][M];
		visit = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			String[] arr = br.readLine().split("");
			for (int j = 0; j < M; j++) {
				map[i][j] = stoi(arr[j]);
			}
		}
		
		bfs();
		System.out.println(cnt);
	}
	
	public static void bfs() {
		Queue<Node> q = new LinkedList<Node>();
		q.add(new Node(0, 0, 1));
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			if(visit[cur.y][cur.x]) continue;
			visit[cur.y][cur.x] = true;
			
			if(cur.y == N -1 && cur.x == M - 1) {
				cnt = cur.step;
				return;
			}
			
			for (int dir = 0; dir < 4; dir++) {
				int ny = cur.y + dy[dir];
				int nx = cur.x + dx[dir];
				
				if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
				if(visit[ny][nx] || map[ny][nx] != 1) continue;
				
				int step = cur.step + 1;
				q.add(new Node(ny, nx, step));
			}
		}
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}