1226번 - 미로1

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

DFS/BFS 알고리즘의 아주 기본적인 문제이다.

카테고리가 큐라서 큐를 이용해서 한 번 DFS/BFS를 구현해보세요! 라는 의미인 듯 하다.

나는 큐를 안썼지만 (...)

 

나중에 따로 DFS/BFS에 대한 포스팅을 할거라 자세한 설명은 추후에 링크 첨부할 예정!

 

 

2. 코드

public class Day6_1226_미로1 {
	// 상하좌우
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };
	static int N = 16;
	static int[][] map = new int[N][N];
	static boolean[][] visited = new boolean[N][N];
	static int result;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder(50);
		
		for (int tc = 1; tc <= 10; tc++) {
			br.readLine(); // 테스트 케이스 번호

			// 입력
			for (int i = 0; i < N; i++) {
				String line = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = line.charAt(j) - '0';
				}
			}

			visited = new boolean[N][N];
			result = 0;
			dfs(1, 1);

			sb.append("#" + tc + " " + result + "\n");
		}
		System.out.println(sb.toString());
	}

	public static void dfs(int y, int x) {
		if (result == 1) {
			return;
		}
		
		// 도착한 경우
		if (isArrive(y, x)) { 
			result = 1;
			return;
		}

		// 상하좌우
		for (int i = 0; i < 4; i++) {
			int newY = y + dy[i];
			int newX = x + dx[i];
			if(check(newY, newX) && !visited[newY][newX]) {
				visited[y][x] = true;
				dfs(newY, newX);
			}
		}
	}

	public static boolean check(int y, int x) {
		if(y < 0 || x < 0 || y >= N || x >= N) return false;
		if(map[y][x] == 1) return false;
		return true;
	}

	public static boolean isArrive(int y, int x) {
		return (map[y][x] == 3) ? true : false;
	}
}

 

 

3. 실행시간

코드는 간결했지만 속도가 조금 느렸다.

 

 

 

 

 

---

💡 느낀 점

• 재귀로 DFS를 구현하니 도착지에 도착해도 호출된 함수 스택을 한 번에 빠져나가지 못해 시간 차이가 나는 것 같다.
• 만약 메인에서 반복문과 큐를 이용한다면 바로 break를 할 수 있기 때문에 시간 단축이 될 것 같다.

---