[SW expert Academy] SWEA 1226번 미로1 자바(Java)

[D4] [S/W 문제해결 기본] 7일차 - 미로1 - 1226

문제 링크

성능 요약

메모리: 21,064 KB, 시간: 156 ms, 코드길이: 1,316 Bytes

제출 일자

2023-11-18 11:41

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

1. 사방이 막힌 미로(인덱스 범위 밖 체크 x)

2. 도착지점 갈 수 있는지 없는지를 판단

3.  - 0: 길, 1: 벽, 2: 출발점, 3:도착점

4. Queue 있어야 함

5. visit 배열 넣어줘서 방문체크

6. Queue에 안넣는 기준

- 값이 1(벽)일 때

- 방문 했을 때

7. 끝나는 기준

- 값이 3(도착점)일 때

- Queue가 비었을 때(도착 못함)

import java.util.*;

class Solution {
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		for (int tc = 1; tc <= 10; tc++) {
			sc.nextInt();
			int[][] map = new int[16][16];
			boolean[][] visit = new boolean[16][16];
			int startX = 0, startY = 0;
			for (int i = 0; i < map.length; i++) {
				String line = sc.next();
				for (int j = 0; j < line.length(); j++) {
					int value = line.charAt(j) - '0';
					map[i][j] = value;
					if (map[i][j] == 2) {
						startX = i;
						startY = j;
					}
				}
			}
			boolean result = bfs(startX, startY, map, visit);
			System.out.println("#" + tc + " " + (result ? "1" : "0"));
		}
	}

	private static boolean bfs(int startX, int startY, int[][] map, boolean[][] visit) {
		int[] dirX = { -1, 1, 0, 0 };
		int[] dirY = { 0, 0, -1, 1 };
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { startX, startY });
		visit[startX][startY] = true;

		while (!queue.isEmpty()) {
			int[] n = queue.poll();

			for (int i = 0; i < 4; i++) {
				int nx = n[0] + dirX[i];
				int ny = n[1] + dirY[i];

				if (map[nx][ny] == 1 || visit[nx][ny]) {
					continue;
				}
				if (map[nx][ny] == 3) {
					return true;
				}

				visit[nx][ny] = true;
				queue.offer(new int[] { nx, ny });
			}
		}
		return false;
	}
}