BFS

너비우선탐색. 아직 설명없음

BFS_Searching (완전탐색)

package Algorithm;

import java.util.Scanner;

class BFS_Searching {

	static final int MAX_VERTEX = 30;

	static int num;
	static int map[][];
	static int visit[];
	static int queue[];
	static int rear, front;

	static void breadthFirstSearch(int vertex)
	{
		visit[vertex] = 1; 
		System.out.print(vertex + " ");
		queue[rear++] = vertex;
		while (front < rear)
		{
			vertex = queue[front++];
			for (int i = 1; i <= num; i++)
			{
				if (map[vertex][i] == 1 && visit[i] == 0)
				{
					visit[i] = 1;
					System.out.printf("%d ", i);
					queue[rear++] = i;
				}
			}
		}
	}

	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();

		for (int test_case = 1; test_case <= T; test_case++)
		{
			map = new int[MAX_VERTEX][MAX_VERTEX];
			visit = new int[MAX_VERTEX];
			queue = new int[MAX_VERTEX];
			
			num = sc.nextInt();
			int start = sc.nextInt();

			while (true)
			{
				int v1 = sc.nextInt();
				int v2 = sc.nextInt();
				if (v1 == -1 && v2 == -1)
				{
					break;
				}
				map[v1][v2] = map[v2][v1] = 1;
			}

			System.out.printf("#%d ", test_case);
			breadthFirstSearch(start);
			System.out.printf("\n");
		}
		
		sc.close();
	}
}

BFS_Algorithm (맵에서 최단거리)

package Algorithm;

import java.util.Scanner;

class Queue
{
	Point queue[];
	int rear;
	int front;
	
	class Point
	{
		int x;
		int y;
		int c;
		
		public Point(int x, int y, int c)
		{
			this.x = x;
			this.y = y;
			this.c = c;
		}
	}
	
	public Queue(int capacity)
	{
		queue = new Point[capacity];
		rear = front = 0;
	}
	
	boolean isEmpty()
	{
		return (rear <= front);
	}
	
	boolean enqueue(int x, int y, int c)
	{
		queue[rear++] = new Point(x, y, c);
		return true;
	}
	
	Point dequeue()
	{
		if (isEmpty())
		{
			return null;
		}
		front++;
		return queue[front-1];
	}
}

class BFS_Algorithm
{
	static final int MAX_N = 50;
	static int[][] MAP;
	static int row;
	static int column;
	
	public static int breadthFirstSearch()
	{
		Queue queue = new Queue(MAX_N * MAX_N);
		queue.enqueue(1, 1, 0);
		MAP[1][1] = 0;
		while(!queue.isEmpty())
		{
			Queue.Point p = queue.dequeue();
			if (p.x == column && p.y == row)//
			{
				return p.c;
			}
			if (p.x + 1 <= column && MAP[p.x + 1][p.y] != 0)
			{
				queue.enqueue(p.x + 1, p.y, p.c + 1);
				MAP[p.x + 1][p.y] = 0;
			}
			if (p.y + 1 <= row && MAP[p.x][p.y + 1] != 0) 
			{
				queue.enqueue(p.x, p.y + 1, p.c + 1);
				MAP[p.x][p.y + 1] = 0;
			}
			if (p.x - 1 > 0 && MAP[p.x - 1][p.y] != 0) 
			{
				queue.enqueue(p.x - 1, p.y, p.c + 1);
				MAP[p.x - 1][p.y] = 0;
			}
			if (p.y - 1 > 0 && MAP[p.x][p.y - 1] != 0) 
			{
				queue.enqueue(p.x, p.y - 1, p.c + 1);
				MAP[p.x][p.y - 1] = 0;
			}
		}
		return -1;
	}
	
	
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++)
		{
			row = sc.nextInt();
			column = sc.nextInt();
			MAP = new int[column+1][row+1];
			for (int i = 1; i <= row; i++){
				for (int j = 1; j <= column; j++)
				{
					MAP[j][i] = sc.nextInt();
				}
			}
			System.out.printf("#%d %d\n", test_case, breadthFirstSearch());
		}
		sc.close();
	}
}