[JAVA] SWEA 1226 미로1 [BFS, DFS]

전체 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class SWEA_1226_미로1 {

	static int[] dy = { 1, -1, 0, 0 }; //상, 하, 우, 좌
	static int[] dx = { 0, 0, 1, -1 };
	static int chk; //도달유무 체크값

	static class Point{ // bfs 사용시 필요한 좌표 클래스
		int y, x;
		Point(int y, int x){
			this.y = y;
			this.x = x;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		for (int test = 1; test <= 10; test++) {
			String trash = sc.next(); //쓰레기값 버리기
			char[][] arr = new char[16][16]; // 값 배열
			boolean[][] v = new boolean[16][16]; // 방문 체크 boolean 배열

			for (int i = 0; i < 16; i++) {
				arr[i] = sc.next().toCharArray();
			}

			chk = 0;
			v[1][1] = true;
			bfs(arr, v);
//			dfs(1, 1, arr, v);
			System.out.println("#" + test + " " + chk);

		}
	}

	private static void bfs(char[][] arr, boolean[][] v) { //BFS
		Queue<Point> q = new LinkedList<Point>(); // Queue 선언
		q.add(new Point(1, 1)); // 시작 좌표는 모든 경우가 (1,1)이므로 첫좌표로 넣어주고 시작
		v[1][1] = true; // 1,1 방문체크
		
		while(!q.isEmpty()) {
			Point p = q.poll(); //q의 끝값을 poll
			for(int i=0; i<4; i++) { //사방 체크
				int ry = p.y + dy[i];
				int rx = p.x + dx[i];
				if(ry>=0 && ry<16 && rx>=0 && rx<16 && !v[ry][rx]) { // ry, rx가 인덱스 내이고, 방문이 안되어있다면
					if(arr[ry][rx] == '3') { // 만약 값이 3이면 chk를 1로 하고 종료
						chk = 1;
						return;
					}else if(arr[ry][rx] == '0') { // 0이라면, 방문체크 후 q에 넣어준다.
						v[ry][rx] = true;
						q.add(new Point(ry, rx));
					} // 1은 자연스럽게 무시된다.
				}
			}
		}
		
	}
	private static void dfs(int y, int x, char[][] arr, boolean[][] v) {
		if(arr[y][x] == '3') {
			chk = 1;
			return;
		}
		for (int i = 0; i < 4; i++) {
			int ry = y + dy[i];
			int rx = x + dx[i];
			if(ry>=0 && ry<16 && rx>=0 && rx<16 && !v[ry][rx]) { // ry, rx가 인덱스 내이고, 방문이 안되어있다면
				if(arr[ry][rx] == '3') { // 만약 값이 3이면 chk를 1로 하고 종료
					chk = 1;
					return;
				}else if(arr[ry][rx] == '0') { // 0이라면
					v[ry][rx] = true; // 방문 체크 후
					dfs(ry, rx, arr, v); // 재귀
					v[ry][rx] = false; // 재귀 끝난 후 다시 false로 변환 후 진행
				} // 1은 자연스럽게 무시된다.
			}
		}
	}

}

 

문제 핵심 코드

 

BFS

private static void bfs(char[][] arr, boolean[][] v) { //BFS
	Queue<Point> q = new LinkedList<Point>(); // Queue 선언
	q.add(new Point(1, 1)); // 시작 좌표는 모든 경우가 (1,1)이므로 첫좌표로 넣어주고 시작
	v[1][1] = true; // 1,1 방문체크
	
	while(!q.isEmpty()) {
		Point p = q.poll(); //q의 끝값을 poll
		for(int i=0; i<4; i++) { //사방 체크
			int ry = p.y + dy[i];
			int rx = p.x + dx[i];
			if(ry>=0 && ry<16 && rx>=0 && rx<16 && !v[ry][rx]) { // ry, rx가 인덱스 내이고, 방문이 안되어있다면
				if(arr[ry][rx] == '3') { // 만약 값이 3이면 chk를 1로 하고 종료
					chk = 1;
					return;
				}else if(arr[ry][rx] == '0') { // 0이라면, 방문체크 후 q에 넣어준다.
					v[ry][rx] = true;
					q.add(new Point(ry, rx));
				} // 1은 자연스럽게 무시된다.
			}
		}
	}
	
}

 

DFS

private static void dfs(int y, int x, char[][] arr, boolean[][] v) {
	if(arr[y][x] == '3') {
		chk = 1;
		return;
	}
	for (int i = 0; i < 4; i++) {
		int ry = y + dy[i];
		int rx = x + dx[i];
		if(ry>=0 && ry<16 && rx>=0 && rx<16 && !v[ry][rx]) { // ry, rx가 인덱스 내이고, 방문이 안되어있다면
			if(arr[ry][rx] == '3') { // 만약 값이 3이면 chk를 1로 하고 종료
				chk = 1;
				return;
			}else if(arr[ry][rx] == '0') { // 0이라면
				v[ry][rx] = true; // 방문 체크 후
				dfs(ry, rx, arr, v); // 재귀
				v[ry][rx] = false; // 재귀 끝난 후 다시 false로 변환 후 진행
			} // 1은 자연스럽게 무시된다.
		}
	}
}

 

이번 문제는 DFS와 BFS가 모두 가능했다. 단순한 경로 찾기 문제여서 가능했다.

 

가능한 경로 문제들은 DFS와 BFS 모두 시도해 보는게 연습에 좋은 영향을 끼치는 것 같다!