프로그래밍/코딩테스트
[탐색] 너비 우선 탐색(BFS)
코드몬스터
2023. 7. 31. 18:38
728x90
💡 먼저 부족하지만 저의 글을 읽어주셔서 감사드립니다!!!
참고 정도로 해주셨으면 좋겠습니다.
해당 강의는 여기 사이트 입니다.
너비 우선 탐색(Breadth First Search)
- 시작 노드에서 인접 노드를 모두 방문하고, 방문한 노드에서 인접 노드를 모두 방문하는 것을 반복
- 그래프 순회 방법 중 하나
- 간선에 가중치를 줄 수 있다?
👉 큐(Queue)
- 보통 Queue는 LinkedList 로 만든다.
public class App {
static final int MAX_N = 10; // 문제에 따라서 최대 노드 개수를 정해줘야 한다. // 어떤 기준으로 정할까?
static int vertex, line;
static int[][] Graph = new int[MAX_N][MAX_N]; // 인접행렬 0과 1
public static void main(string[] args) {
Scanner sc = new Scanner(System.in);
vertex = sc.nextInt();
line = sc.nextInt();
for (int i = 0; i < line; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
Graph[v][u] = Graph[u][v] = 1;
}
bfs(0);
}
public static void bfs(int node) {
boolean[] visited = new boolean[MAX_N];
Queue<Integer> myqueue = new LinkedList<>();
visited[node] = true;
myqueue.add(node);
while(!myqueue.isEmpty()) {
int curr = myqueue.remove();
System.out.println(curr + " ");
for (int next = 0; next < N; next++) {
if(!visted[next] && Graph[curr][next] != 0) {
visited[next] = true;
myqueue.add(next);
}
}
}
}
}
👉 Shortest path
public class App {
static final int MAX_N = 10; // 문제에 따라서 최대 노드 개수를 정해줘야 한다. // 어떤 기준으로 정할까?
static int[][] D = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 방향 움직이는 2차원 배열
static int vertex;
static int[][] Graph = new int[MAX_N][MAX_N]; // 인접행렬 0과 1
static class Point {
int row, col, dist;
Point(int r, int c, int d) {
row = r; col = c; dist = d;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
vertex = sc.nextInt();
for (int i = 0; i < vertex; i++) {
for (int j = 0; j < vertex; j++) {
Graph[i][j] = sc.nextInt();
}
}
int sRow, sCol, dRow, dCol;
sRow = sc.nextInt(); sCol = sc.nextInt();
dRow = sc.nextInt(); dCol = sc.nextInt();
System.out.println(bfs(sRow, sCol, dRow, dCol));
}
public static int bfs(int sRow, int sCol, int dRow, int dCol) {
boolean[][] visited = new boolean[MAX_N][MAX_N];
Queue<Point> myqueue = new LinkedList<>();
visited[sRow][sCol] = true;
myqueue.add(new Point(sRow, sCol, 0)); // 시작점 추가
while (!myqueue.isEmpty()) {
Point curr = myqueue.remove();
if (curr.row == dRow && curr.col == dCol)
return curr.dist;
for (int i = 0; i < 4; i++) { // 4의 의미는 상하좌우
int nr = curr.row + D[i][0], nc = curr.col + D[i][1];
if (nr < 0 || nr > vertex -1 || nc < 0 || nc > vertex - 1) continue; // 상하 좌우 가장자리 체크
if (visited[nr][nc]) continue; // 방문 여부 체크
if (Graph[nr][nc] == 1) continue; // 배열에서 1은 벽을 의미
visited[nr][nc] = true;
myqueue.add(new Point(nr, nc, curr.dist + 1));
}
}
return -1;
}
}