[Baekjoon] 6832_Maze

문제(출처: https://www.acmicpc.net/problem/6832)

---

< Maze >

 

문제 풀이 

 

bfs 알고리즘을 활용하여 

+ : 상하좌우
- : 좌우
| : 상하
* : 이동 불가

에 맞게 이동한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class _6832_ { // Maze
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	static char arr[][];
    
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
		int t = Integer.parseInt(bf.readLine());
		for (int i = 0; i < t; i++) {
			int r = Integer.parseInt(bf.readLine());
			int c = Integer.parseInt(bf.readLine());
            
			arr = new char[r][c];
			for (int j = 0; j < r; j++) {
				String str = bf.readLine();
				for (int k = 0; k < c; k++) {
					arr[j][k] = str.charAt(k);
				}
			}
			if (r == 1 && c == 1 && arr[0][0]!='*') {
				bw.write("1\n");
			} else {
				bw.write(bfs() + "\n");
			}
		}
		bw.flush();
	}
    
	private static int bfs() {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { 0, 0, 1 });
        
		boolean visited[][] = new boolean[arr.length][arr[0].length];
		visited[0][0] = true;
        
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
            
			if (arr[temp[0]][temp[1]] == '+') {
				for (int k = 0; k < 4; k++) {
					int x = temp[0] + dx[k];
					int y = temp[1] + dy[k];
					if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && arr[x][y] != '*' && !visited[x][y]) {
						if (x == arr.length - 1 && y == arr[0].length - 1) {
							return temp[2] + 1;
						}
						visited[x][y] = true;
						queue.add(new int[] { x, y, temp[2] + 1 });
					}
				}
			} else if (arr[temp[0]][temp[1]] == '-') {
				for (int k = 2; k < 4; k++) {
					int x = temp[0] + dx[k];
					int y = temp[1] + dy[k];
					if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && arr[x][y] != '*' && !visited[x][y]) {
						if (x == arr.length - 1 && y == arr[0].length - 1) {
							return temp[2] + 1;
						}
						visited[x][y] = true;
						queue.add(new int[] { x, y, temp[2] + 1 });
					}
				}
			} else if (arr[temp[0]][temp[1]] == '|') {
				for (int k = 0; k < 2; k++) {
					int x = temp[0] + dx[k];
					int y = temp[1] + dy[k];
					if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && arr[x][y] != '*' && !visited[x][y]) {
						if (x == arr.length - 1 && y == arr[0].length - 1) {
							return temp[2] + 1;
						}
						visited[x][y] = true;
						queue.add(new int[] { x, y, temp[2] + 1 });
					}
				}
			}
		}
		return -1;
	}
}

변수)
dx, dy : 이동 방향
t : 테스트 케이스 개수
r, c : 배열 크기
visited : 방문 여부

 

테스트 케이스 수를 입력받아 테스트 케이스 수만큼 다음 과정을 반복한다.

1) 배열 크기 입력

2) 배열 크기만큼 배열 정보 입력받아 arr에 저장

3) 배열 크기가 1x1이고 값이 *라면 -1 출력, *가 아니라면 1 출력

4) 배열 크기가 1x1이 아니라면 bfs 함수 반환값 출력

 

bfs()

Queue에 시작 위치와 이동 횟수를 저장한다. 시작 위치를 방문처리한다. Queue가 빌 때까지 다음 과정을 반복한다.

1) Queue poll

2) 현재 값이 +라면 상하좌우로 이동하여 배열 범위 안이고 값이 *이 아니며 아직 방문하지 않은 곳이라면 방문 처리 및 queue에 추가. 도착위치라면 temp[2]+1 반환

3) 현재 값이 -라면 좌우로 이동하여 배열 범위 안이고 값이 *이 아니며 아직 방문하지 않은 곳이라면 방문 처리 및 queue에 추가. 도착위치라면 temp[2]+1 반환

4) 현재 값이 |라면 상하로 이동하여 배열 범위 안이고 값이 *이 아니며 아직 방문하지 않은 곳이라면 방문 처리 및 queue에 추가. 도착위치라면 temp[2]+1 반환

도착 위치까지 이동할 수 없다면 -1 반환

---

---