ALGORITHM

JAVA ๋ฏธ๋กœํƒ์ƒ‰ / BFS

girin_dev 2022. 6. 14. 22:00
728x90
๋ฐ˜์‘ํ˜•

 

 

๐Ÿ˜’ BFS / Breadth-First Search / ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ 

 

๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ : 

    ํ•˜๋‚˜์˜ ์ •์ ์—์„œ ์‹œ์ž‘ํ•ด์„œ ์ฐจ๋ก€๋กœ ๋ชจ๋“  ์ •์ ์„ ๋ฐฉ๋ฌธํ•˜๊ฒŒ ๋œ๋‹ค. 

 

    ๋”ฐ๋ผ์„œ ํŠน์ • ๋„์‹œ์—์„œ ๋‹ค๋ฅธ ๋„์‹œ๋กœ ๊ฐ€๊ฑฐ๋‚˜, ๋ฏธ๋กœ์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ๊ฑฐ๋‚˜,

 

 

๋ณดํ†ต์€ ๋‘ ์ขŒํ‘œ ์‚ฌ์ด์˜ ( ๋…ธ๋“œ ์‚ฌ์ด์˜ ) ์ตœ๋‹จ ๊ฒฝ๋กœ ํ˜น์€ ์ž„์˜ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด ์“ด๋‹ค. 

 

๐Ÿฅ• ๊ตฌํ˜„ ์‹œ, ํŠน์ • ์ขŒํ‘œ ( ๋…ธ๋“œ ) ๋ฅผ ๋ฐฉ๋ฌธํ•œ๊ฒƒ์— ๋Œ€ํ•œ ์—ฌ๋ถ€๋ฅผ ๋ฐ˜๋“œ์‹œ ๊ฒ€์‚ฌํ•ด์•ผ ํ•œ๋‹ค. 

 

    ๊ฒ€์‚ฌํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด ๋ฌดํ•œ ๋ฃจํ”„์— ๋น ์งˆ ์œ„ํ—˜์ด ์กด์žฌํ•œ๋‹ค. 

 

๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ๋ฅผ  ์ฐจ๋ก€๋กœ ๊บผ๋‚ผ ์ˆ˜ ์žˆ๋Š” ์ž๋ฃŒ ๊ตฌ์กฐ์ธ Queue ๋ฅผ ์‚ฌ์šฉ. ์ฆ‰ ์„ ์ž…์„ ์ถœ์ด ์›์น™์ด๋‹ค.

 

 

๐Ÿฅ• ์™œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๊ฐ€ ๋˜๋Š”๊ฐ€ ? 

 

https://wikidocs.net/125662 ์ฐธ์กฐ : 

 

https://wikidocs.net/125662


๋ฏธ๋กœํƒ์ƒ‰๊ณผ ๊ฐ™์€ ๋ฌธ์ œ๋ฅผ BFS๋ฅผ ๊ตฌํ˜„ํ•˜๋‹ค๋ณด๋ฉด, ๋ˆ„๊ตฌ๋‚˜ ํ•œ ๋ฒˆ์”ฉ์€ ์˜๊ตฌ์‹ฌ์„ ๊ฐ–๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ๊ณ„์†ํ•ด์„œ visited๋ฅผ ํ†ตํ•ด ๊ฒฝ๋กœ๋ฅผ ์ฐ์–ด ๋ณด๋ฉด์„œ๋„, "์ด ๊ฒฝ๋กœ๊ฐ€ ์ •๋ง ์ตœ์  ๊ฒฝ๋กœ๊ฐ€ ๋งž์„๊นŒ?" ๋˜๋Š” "ํ˜น์‹œ ๋‹ค๋ฅธ ๊ฒฝ๋กœ๋ฅผ ํ†ตํ•ด์„œ ๊ฐ€๋ฉด ์ตœ์†Œ๊ฐ’์„ ๊ฐ–๊ฒŒ ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ์ƒ๊ธธ ์ˆ˜ ๋„ ์žˆ์ง€ ์•Š์„๊นŒ?" ๊ฐ™์€ ์˜๋ฌธ์ด ๋“ค๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.
์ฒœ์ฒœํžˆ ์ƒ๊ฐํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ๊ฐ€์žฅ ๋จผ์ € ์‹œ์ž‘์ ์— ์ค€ํ•˜๋Š” ์ขŒํ‘œ์˜ visited ๋ฐฐ์—ด์—๋Š” ์ถœ๋ฐœ์ง€๋ฅผ ๋œปํ•˜๋Š” 1์„ ํ‘œ๊ธฐํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‘ ๋ฒˆ ์งธ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๊ฒฝ๋กœ์—๋Š” 2๊ฐ€, ์„ธ ๋ฒˆ๋งŒ์— ๋„๋‹ฌ์ด ๊ฐ€๋Šฅํ•œ ๊ณณ์—๋Š” ๋ชจ๋‘ 3์ด ํ‘œ๊ธฐ๋ฉ๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ vistied๋ฐฐ์—ด์—๋Š” ๋ชจ๋“  ์ˆœ๊ฐ„ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ตœ์„ ์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๊ธฐ์ž…๋˜๋Š” ๊ฒƒ์ด์ง€์š”. ๋‹ค๋ฅธ ๋ง๋กœ ํ‘œํ˜„ํ•ด๋ณด๋ฉด, ๋‚ด๊ฐ€ ์ด๋ฒˆ์— ํƒ์ƒ‰ํ•ด์„œ ๋ฐœ๊ฒฌํ•œ ๋…ธ๋“œ๊ฐ€ ์ด๋ฏธ ์ด์ „์— ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ๋ผ๋ฉด, ๊ธฐ์กด์— ์ฑ„์›Œ์ง„ ๊ฐ’์€ ์ƒˆ๋กœ ์ฑ„์šฐ๋ ค๋Š” ๊ฐ’๋ณด๋‹ค ํ•ญ์ƒ ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์„ ์ˆ˜ ๋ฐ–์— ์—†๋‹ค๋Š” ๋œป ์ž…๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์šฐ๋ฆฌ๋Š” ํ•ด๋‹น ๋…ธ๋“œ์˜ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€(if(visited[i][j]==0)) ๋งŒ ํ™•์ธํ•˜๊ฒŒ ๋˜๋Š” ๊ฒƒ์ด์ง€์š”.

 

๋ฌผ๊ฒฐ์˜ ํŒŒ๋™์— ๋น„์œ ํ•œ ์„ค๋ช…๋„ ์žˆ๋‹ค.

๋™์‹œ์— ๋‹ค๋ฅธ ๋…ธ๋“œ๋ฅผ ๊ณ„์†ํ•ด์„œ ์ฑ„์›Œ๊ฐ€๊ณ , ์ฑ„์›Œ ๊ฐ„ ๊ณณ์€ ๋ฐฉ๋ฌธํ–ˆ๋‹ค๋Š” ๊ธฐ๋ก์„ ๋‚จ๊ธฐ๊ธฐ ๋•Œ๋ฌธ์—.

 

 

๊ตฌํ˜„ : 

 

 

// ํด๋ž˜์Šค๋กœ ๋‹ด์•„์„œ ์“ด๋‹ค. 
class Location { 
    int row;
    int col;
    int dist;
    public Location(int row, int col, int dist) {
        this.row = row;
        this.col = col;
        this.dist = dist;
    }
}


////  ์ขŒ์šฐ ์ƒํ•˜ ๊ฐ„๊ฒฉ๊ณผ ๋ฏธ๋กœ๋ฅผ ๋‹ด์„ ๋ฐฐ์—ด ๊ทธ๋ฆฌ๊ณ  ๋ฐฉ๋ฌธ ์—ฌ๋ถ€ ์ฒดํฌ ๋ฐฐ์—ด

static int charNums;
static int linkNums;
static String arr[][];
static boolean[][] visited;

////

public static void main(String[] args) {

    maze();

    chk = new int[lineNums][charNums];
    visited = new boolean[lineNums][charNums];
	
    // ์‹œ์ž‘์ ์€ ๋ฐฉ๋ฌธํ•˜๊ณ , 
    visited[1][0] = true;
    // A ์ขŒํ‘œ๋ถ€ํ„ฐ ์ถœ๋ฐœํ•œ๋‹ค.
    int answer = findPath(1,0);

    System.out.println(" ์ •๋‹ต : " + answer);
}




public static int findPath(int x, int y) {

        Queue<Location> queue = new LinkedList<>();

        int[] xArr = {0,0,-1,1,};
        int[] yArr = {-1,1,0,0,};

        queue.add(new Location(x,y,1));
        visited[x][y] = true;
        while(!queue.isEmpty()) {
            Location location = queue.poll();

            int row = location.row;
            int col = location.col;
            int dist = location.dist;

			// ๋ชฉ์ ์ง€๋Š” 'B' ์ด๋‹ค 
            if (arr[row][col].equals("B")) {
                System.out.println(" ๋„์ฐฉ : " + arr[row][col]);
                return dist;
            }

            for (int i = 0; i < 4; i ++ ) {
                // ์ƒํ•˜์ขŒ์šฐ ๋ฐฐ์—ด์„ ํ†ตํ•ด ์ƒํ•˜์ขŒ์šฐ ์œ„์น˜๋ฅผ ๋ชจ๋‘ ์ฐพ๋Š”๋‹ค.
                int nextX =  row + xArr[i];
                int nextY =  col + yArr[i];

				//๋ฐฉ๋ฌธํ–ˆ๋Š”๊ฐ€? ๋ฐฉ๋ฌธํ• ์ˆ˜์žˆ๋Š”๊ฐ€?
                if (checkLocation(nextX,nextY) && !visited[nextX][nextY]) {
                    
                    // ํ•˜, ์šฐ  ๋ชจ๋‘ ๋ฐฉ๋ฌธ ๊ฐ€๋Šฅํ•˜๋‹ค๋ฉด, 
                    // ํ์—๋Š” 2๊ฐœ์˜ ๋ฐฉํ–ฅ์ด ๋™์‹œ์— ๋“ค์–ด๊ฐ„๋‹ค.
                    queue.add(new Location(nextX, nextY, dist+1));
                    
                    // ๋ฐฉ๋ฌธ ๊ธฐ๋ก.
                    visited[nextX][nextY] = true;
                }

            }
        }

        return 0;
    }

 

๋ฐฉ๋ฌธ ์ฒดํฌ.

  // ๋ฐฉ๋ฌธ ์—ฌ๋ถ€ ์ฒดํฌ 
  public static boolean checkLocation (int nextX, int nextY) {

        if (nextX < 0 || nextX >= charNums || nextY < 0 || nextY >= lineNums || arr[nextX][nextY].equals("0")) {
            return false;
        }
        return true;
  }

 

 

๋ฏธ๋กœ :

     0์€ ๋ชป์ง€๋‚˜๊ฐ„๋‹ค.

 

๋ฏธ๋กœ ๋ฐฐ์—ด : 


      String mazes =
                "0000000000000000000000000000000000000000000000000000000000000000\n" +
                "A             000                                            000\n" +
                "0000000000000 000 000000000000000000 00 0000000000000000000 00 0\n" +
                "0        0 00 0                   00 00 0   00     0      0  0 0\n" +
                "0000 000 0 00 0 00000000000000000 00 00 000  00 00 0 0000 00 0 0\n" +
                "0    0 0 0 00 0  0000           0 00 00 0000000000 0 0000000 0 0\n" +
                "0 00 0 0 0 00 0       000000000 0 00 00            0 0       0 0\n" +
                "0           0 0000 0 0       0 000000000000 0 000000 00000000000\n" +
                "0 00000000000   0  0 0 0000000              0 0                0\n" +
                "0      0000   0 0 00 000000  0000000000000000 000000 000000000 0\n" +
                "0 0000     00                                                0 B\n" +
                "0000000000000000000000000000000000000000000000000000000000000000";

 

320x100
๋ฐ˜์‘ํ˜•