그래프 문제(bfs,dfs) #2178: 미로 탐색 [JAVA]

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

---

 

 

 

문제 접근

 

 

 

최단 거리니까 bfs를 쓰자. 왜 bfs를 써야하는지는 이전 포스팅 '그래프 탐색 bfs, dfs 정리'를 참조하시라

 

 

 

 

 

 

 

코드1

 

 

 

 

Point 클래스에 행,열 위치와 거리를 저장해서 큐에 저장.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Point {
	int c;
	int r;
	int cnt;

	Point(int c, int r, int cnt) {
		this.c = c;
		this.r = r;
		this.cnt = cnt;
	}
}

public class Main {
	static int n, m;

	static int[][] maze;
	static boolean[][] visited;
	static int[] dc = { -1, 0, 0, 1 };
	static int[] dr = { 0, -1, 1, 0 };

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		maze = new int[n + 1][m + 1];
		visited = new boolean[n + 1][m + 1];

		for (int i = 1; i <= n; i++) {
			String s = br.readLine();
			for (int j = 1; j <= m; j++) {
				maze[i][j] = s.charAt(j - 1) - '0';
			}
		}

		bfs(1, 1);

	}

	private static void bfs(int x, int y) {
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(x, y, 1));
		visited[x][y] = true;

		while (!q.isEmpty()) {
			Point p = q.poll();

			for (int i = 0; i < 4; i++) {
				int nc = p.c + dc[i];
				int nr = p.r + dr[i];

				if (nc < 1 || nr < 1 || nc > n || nr > m)
					continue;

				if (visited[nc][nr] || maze[nc][nr] == 0)
					continue;

				if (nc == n && nr == m) {
					System.out.println(p.cnt + 1);
					return;
				}

				visited[nc][nr] = true;
				q.add(new Point(nc, nr, p.cnt + 1));

			}
		}
	}
}

 

 

 

 

 

 

 

 

코드2

 

 

 

 

큐에 int[] 배열로 행,열 위치 저장, 거리는 그래프를 표현한 인접행렬 maze에 덮어씌움.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static int n, m;

	static int[][] maze;
	static boolean[][] visited;
	static int[] dc = { -1, 0, 0, 1 };
	static int[] dr = { 0, -1, 1, 0 };

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		maze = new int[n + 1][m + 1];
		visited = new boolean[n + 1][m + 1];

		for (int i = 1; i <= n; i++) {
			String s = br.readLine();
			for (int j = 1; j <= m; j++) {
				maze[i][j] = s.charAt(j - 1) - '0';
			}
		}

		bfs(1, 1);

	}

	private static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] { x, y });
		visited[x][y] = true;

		while (!q.isEmpty()) {
			int p[] = q.poll();
			int pc = p[0];
			int pr = p[1];

			for (int i = 0; i < 4; i++) {
				int nc = pc + dc[i];
				int nr = pr + dr[i];

				if (nc < 1 || nr < 1 || nc > n || nr > m)
					continue;

				if (visited[nc][nr] || maze[nc][nr] == 0)
					continue;

				if (nc == n && nr == m) {
					System.out.println(maze[pc][pr] + 1);
					return;
				}

				visited[nc][nr] = true;
				q.add(new int[] { nc, nr });
				maze[nc][nr] = maze[pc][pr] + 1;
			}
		}
	}
}

 

 

 

 

성능 차이는 없삼