[백준 알고리즘] 2178 미로 탐색 (21.05.02)

이전 이야기 ....

 

2021.05.02 - [알고리즘 스터디] - [백준 알고리즘] 11724 연결 요소의 개수 (21.05.02)

[백준 알고리즘] 11724 연결 요소의 개수 (21.05.02)

 

 

 

오늘은 무려 40분을 일찍 끝내버려서

 

아쉬운? 마음에

 

1문제를 더 풀었습니다!!!!!!!!

.

.

.

 

 

 

그래서 

 

마지막 문제는 오랜만에 미로 탐색!!!

 

 

백준 2178 미로 탐색

 

 

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

 

문제 사이트 : www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

---

 

여기서 핵심 포인트!!!

 

 

-  Maze 구현!!

 

- 탐색을 어떻게 할 것인가?

 

---

 

 

 

 

직접 작성해본 소스코드 및 간단한 설명

 

import java.util.Scanner;

public class Maze { //2178
	
	private static int[][] maze;
	private static int row, col;
	private static boolean done = false;
	private static int count = 0;
	
	static boolean isValid(int r, int c) {
		System.out.println("r : " +r +" c : "+c);
		if( r < 0 || c < 0 || r >= row || c >= col) return false;
		else return (maze[r][c] == 1 || maze[r][c] == 3);
	}
	
	static void search(int r, int c) {
		if(done) return;
		if(r == row && c == col) {
			done = true;
			return;
		}
		
		maze[r][c] = 2;
		count++;
		if(isValid(r-1,c)) search(r-1,c);
		if(isValid(r,c-1)) search(r,c-1);
		if(isValid(r+1,c)) search(r+1,c);
		if(isValid(r,c+1)) search(r,c+1);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		row = sc.nextInt();
		col = sc.nextInt();
		
		maze = new int[row][col];
		
		String tmp = null;
		for(int i = 0; i< row; i++) {
			tmp = sc.next();
			String [] ary = tmp.split("");
			for(int j = 0; j< ary.length; j++) {
				maze[i][j]= Integer.parseInt(ary[j]);
			}
		}
		maze[row-1][col-1] = 3;
		
		search(0,0);
		
		System.out.println(count);
		
	}

}

 

 

사실 이건 미완성 코드인데

왜냐하면 Maze 만 구현해놓고

 

 

 

최소 탐색을 안 해놨기 때문!!!!!!!!

 

 

 

 

 

 

 

그러므로,, 딱히 할 말이 없다................................................

 

 

 

.

.

.

 

 

 

 

 

 

시간 부족으로 다른 친구들도 못했으므로

 

할 말이 더 없다....

 

 

 

 

 

 

 

 

 

그럼 이번주는 이걸로 끝!!!!!!!

 

 

빈센조 보러 가야지^_^ 오늘이 마지막회다^_^

 

 

 

 

---

---

 

 

210508

 

알고리즘 스터디 깃헙에 올리기

 

2시간쯤 전 ㅎㅎ...

 

 

 

 

 

수정한 소스코드 및 간단한 설명

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
	
class Point {
	int x;
	int y;

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

public class Maze { //2178
	
	private static int[][] maze;
	private static int row, col;
	private static boolean[][] visited;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		row = sc.nextInt();
		col = sc.nextInt();
		
		maze = new int[row][col];
		visited = new boolean[row][col];
		
		String tmp = null;
		for(int i = 0; i< row; i++) {
			tmp = sc.next();
			String [] ary = tmp.split("");
			for(int j = 0; j< ary.length; j++) {
				maze[i][j]= Integer.parseInt(ary[j]); // tmp.charAt(j)-'0'; 도 같은 기능!
				visited[i][j] = false;
			}
		}
		
		visited[0][0] = true;
		BFS(0,0);
		System.out.println(maze[row-1][col-1]);
	}

	
	private static void BFS(int x, int y) {
		Queue<Point> q = new LinkedList<Point>();
        q.add(new Point(x, y));
        while (!q.isEmpty()) {
        	Point d = q.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = d.x + dx[i];
                int nextY = d.y + dy[i];
                
                if (nextX < 0 || nextY < 0 || nextX >= row || nextY >= col) {
                    continue;
                }
                if (visited[nextX][nextY] || maze[nextX][nextY] == 0) {
                    continue;
                }
                q.add(new Point(nextX, nextY));
                
                maze[nextX][nextY] = maze[d.x][d.y] + 1;
                
                visited[nextX][nextY] = true;
            }
        }
	}


}

 

 

이번 코드의 중요 포인트는 바로바로

 

 

 

• DFS보다 BFS를 사용하는 것이 좋다!!!! (성능 상 더 좋음)

 

• JAVA에서 .charAt(j)-'0' 을 사용하면 숫자가 나온다는 점!!

 

• 따로 카운팅하는 대신 maze 배열에 카운트하기!!

 

 

 

 

 

 

---

 

 

 

백준 알고리즘

 

채점 결과!!!

 

 

 

다행히 맞았습니다!!

 

 

백준 알고리즘 2178번 채점 결과

 

 

 

 

 

 

---

 

 

 

 

이번 코드는 너무 어려워서 ....

.

.

.

 

 

서칭을 많이 했다 ^^

 

 

 

 

 

 

 

 

 

 

 

 

 

 

그래서 참고한 블로그들을 첨부하자면,

 

 

zoonvivor.tistory.com/77

[BOJ] 백준 2178 - 미로찾기 (자바)

velog.io/@juhyun7793/%EB%B0%B1%EC%A4%80-2178-%EB%AF%B8%EB%A1%9C%EC%B0%BE%EA%B8%B0-Java

백준 2178 미로찾기 (Java)

 

 

 

 

그리고 좀 더 자세한 설명을 원한다면

 

 

 

우리 공희의 블로그를 보시길 바랍니다!!!!!!!!!!!!!

 

blog.naver.com/judy6647/222238274549

PART 02 [실전 문제 #4] DFS/BFS_ 미로 탈출

 

 

아주 잘 설명되어있기 때문!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

그렇다면 안녕!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!