BFS 예제 코드

 

자바로 간단한 예제 코드를 보자면 아래와 같다. 아래 코드는 알고리즘 블로그를 운영 중이신 케로츄 님의 도움을 받아 작성한 예제 코드이다.(https://blog.naver.com/kerochuu)

public class BFS_EX {

	private static class Node {
		int x, y;

		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static int row, col;
	static int[][] map;
	static Queue<Node> q = new LinkedList<Node>();
	static boolean[][] visit;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);

		col = input.nextInt();
		row = input.nextInt();

		map = new int[row][col];
		visit = new boolean[row][col];

		for(int i = 0; i < row; i++) {
			for(int j = 0; j < col; j++) {
				map[i][j] = input.nextInt();
				if(map[i][j] == 1) {
					visit[i][j] = true;
					q.add(new Node(i, j, 0));
				}
			}
		}

		bfs();
	}

	private static void bfs() {
		while(!q.isEmpty()) {
			Node n = q.poll();

			for(int i = 0; i < 4; i++) {
				int nx = n.x + dx[i];
				int ny = n.y + dy[i];

				if(nx >= 0 && ny >= 0 && nx < row && ny < col) {
					if(!visit[nx][ny] && map[nx][ny] >= 0) {
						visit[nx][ny] = true;
						q.add(new Node(nx, ny, n.step + 1));
						map[nx][ny] = n.step + 1;
					}
				}
			}
		}
	}
}

 

해당 코드를 보면 2차원 배열을 만들어 0과 1의 값을 넣고 갈 수 있는 곳과 못 가는 곳을 정해두고 최단 거리로 해당 맵을 빠져나가는 코드이다. bfs 메소드를 보면 맵을 저장해둔 노드들을 탐색하면서 해당 노드의 상하좌우를 탐색한다(상하좌우이기에 기존에 만든 dx, dy를 조합하여 4방향으로 돌리며 상하좌우를 탐색). 그러면서 지나가게 된 장소는 visit 배열의 값을 변경시키고 map배열에 현재 count 값에서 1을 더한 값들을 더해 최종 값을 가지게 한다.