[Java] 너비우선탐색 (BFS) 미로찾기 Queue구현

2022. 7. 16. 00:40·Java/코딩테스트 연습 & 실습
목차
  1. 。。。

너비우선탐색(BFS) 최대한 넓게 이동한 후 더 이상 갈 수 없을 경우 아래로 이동한다.

인접한 노드를 먼저 탐색하고, 가장 멀리 떨어져 있는 정점을 가장 나중에 방문한다.

 

최단 경로를 찾고자 할 경우 주로 사용한다.


1. map : 갈 수 있는 길은 0, 갈 수 없는 길은 1이다.

 

2. enqueue한 길도 벽으로 변경하여 여러번 enqueue할 수 없도록 한다. (방문 처리)

 

3. class Index : Queue에 담을 객체 ( x와 y의 좌표를 가지고 있다.)

 

4. 현재 인덱스를 저장하고 있는 Index 클래스를 매개변수로 받아

     findWay() 메서드에서 상하좌우를 탐색하고 enqueue한다.

 

5. enqueue한 Index를 dequeue해 위치를 이동한다. <- while 반복 : 종료 위치에 도착할 때 까지.

 

import java.util.LinkedList;
import java.util.Queue;

public class BfsQueue {
	public static void main(String[] args) {
		// 7(골인)을 찾을때 까지 너비우선탐색
		bfs(0,0);
	}
	
	//지도
	public static int[][] map = 
			{{0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
			{0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
			{0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
			{0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,1,0,0,0,0},
			{0,1,0,1,0,1,1,1,1,1,1,0,1,0,0,1,0,1,0,1,0,1,1,1},
			{0,1,0,1,0,1,0,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0},
			{0,1,0,1,0,1,1,1,1,0,1,0,0,0,0,1,0,1,0,1,1,1,1,0},
			{0,0,0,1,0,0,0,0,0,0,1,1,1,1,0,1,0,1,0,0,0,0,0,0},
			{0,1,1,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,1,0,1,0,1},
			{0,0,0,0,1,1,1,0,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0},
			{1,0,1,0,1,0,0,0,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1},
			{0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0},
			{0,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0},
			{0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0},
			{1,0,1,0,0,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0},
			{1,0,1,1,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0},
			{1,0,0,0,0,0,1,0,1,0,1,1,1,0,1,0,1,0,0,0,1,0,0,0},
			{1,0,1,1,1,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,1,1},
			{1,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,1,0,0,0,0,1,0,1},
			{1,1,1,1,1,1,1,0,1,0,1,0,0,0,0,0,1,1,1,1,1,1,0,1},
			{0,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,0,1,0,0,0,0,0,1},
			{0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,1,1,1,1,1},
			{0,0,0,0,1,0,0,0,1,0,1,1,1,1,0,1,0,0,0,0,0,0,0,0},
			{1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0}};
		
	public static int size = map.length;
	
	//들린 곳 체크
	public static boolean[][] visit = new boolean[size][size];
	
	//인덱스를 저장하는 큐
	public static Queue<Index> mq = new LinkedList<>();
	
	//너비우선탐색
	public static void bfs(int x, int y) { //시작 행, 열
		Index curr = new Index(x,y);
		map[x][y] = 1; // 첫 위치 visist설정
		
		while(true) {
			if(curr.getX() == size - 1 && curr.getY() == size - 1) { // 골인지점 설정
				System.out.println("미로탈출 완료!");
				break;
			} else {
				findWay(curr); // 현재 위치를 기준으로 길 탐색
				Index temp = mq.poll();
				visit[temp.getX()][temp.getY()] = true; // 이동했으니 true
				System.out.println("" + temp.getX() + " " + temp.getY() + "로 이동");
				curr.setX(temp.getX()); // 현재 위치를 poll으로 변경
				curr.setY(temp.getY());
			}
		}
	}
	
	
	// 현재 위치의 상하좌우 탐색 메서드
	public static void findWay(Index curr) {
		int x = curr.getX();
		int y = curr.getY();
		
		// 위 탐색
		if (x > 0) {
			if (map[x-1][y] != 1) { //벽이 아니면 추가
				mq.offer(new Index(x - 1, y));
				map[x-1][y] = 1; //추가하고 벽으로 만들어버림
			}
		}
		
		// 왼쪽 탐색
		if (y > 0) {
			if (map[x][y-1] != 1) { 
				mq.offer(new Index(x, y-1));
				map[x][y-1] = 1;
			}
		}
		
		// 오른쪽 탐색
		if (y < size-1) {
			if (map[x][y+1] != 1 && !visit[x][y+1]) { 
				mq.offer(new Index(x, y + 1));
				map[x][y+1] = 1;
			}
		}

		// 아래 탐색
		if (x < size-1) {
			if (map[x+1][y] != 1) { 
				mq.offer(new Index(x + 1, y));
				map[x+1][y] = 1;
			}
		}
	}
}

 

class Index

class Index {
	private int x;
	private int y;
	
	public Index() {
	}
	
	public Index(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	public int getY() {
		return y;
	}
	public void setY(int y) {
		this.y = y;
	}
}

。。。

 

'Java > 코딩테스트 연습 & 실습' 카테고리의 다른 글

[Java] 자바 네트워크 채팅 프로그램 구현 ( 소켓, 유니 캐스팅 )  (0) 2022.09.02
[Java] 깊이우선탐색 (DFS) 미로찾기 스택구현  (2) 2022.07.15
[Java] 스택을 이용한 후위표기 계산기  (0) 2022.07.14
[Java] 이진검색 재귀함수로 구현하기  (0) 2022.07.13
[Java] (실습) Baby-gin  (1) 2022.07.11
  1. 。。。
'Java/코딩테스트 연습 & 실습' 카테고리의 다른 글
  • [Java] 자바 네트워크 채팅 프로그램 구현 ( 소켓, 유니 캐스팅 )
  • [Java] 깊이우선탐색 (DFS) 미로찾기 스택구현
  • [Java] 스택을 이용한 후위표기 계산기
  • [Java] 이진검색 재귀함수로 구현하기
현기
현기
  • 현기
    현기의 개발블로그
    현기
  • 전체
    오늘
    어제
    • 분류 전체보기 (120)
      • Front-End (39)
        • Next (5)
        • React (8)
        • React Native (11)
        • Flutter (0)
        • Vue (1)
        • JSP (9)
        • HTML, CSS, JS (5)
      • Back-End (16)
        • Node.js (3)
        • Spring (8)
        • Flask (1)
        • AWS (4)
      • DB (5)
        • Oracle (4)
        • MySQL (1)
      • Python (7)
      • Java (27)
        • 자바 이론 (17)
        • 코딩테스트 연습 & 실습 (10)
      • 자료구조 & 알고리즘 (7)
        • 코딩테스트 (6)
        • 알고리즘 (1)
      • 블록체인 (0)
      • 프롬프트 엔지니어링 (0)
      • CS 지식 (5)
      • IT뉴스 (0)
      • 일상 (3)
      • etc (11)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    쓰레드
    오라클
    티스토리챌린지
    서블릿
    REST API
    자바
    react-native-chart-kit
    Express
    react
    React Native
    포스트맨
    node.js
    React Native Chart
    Python
    자바스크립트
    Java
    JDBC
    오블완
    IS-A
    상속
    JSP
    스택
    리액트 네이티브
    자바 스프링
    파이썬
    next-intl
    Spring
    큐
    그리디
    DI
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.1
현기
[Java] 너비우선탐색 (BFS) 미로찾기 Queue구현
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.