[SWEA] 미로 1

문제

16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.

가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.

주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.

입력

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도달 가능 여부를 1 또는 0으로 표시한다 (1 - 가능함, 0 - 가능하지 않음).

예제 입력

1
1111111111111111
1210000000100011
1010101110101111
1000100010100011
1111111010101011
1000000010101011
1011111110111011
1010000010001011
1010101111101011
1010100010001011
1010111010111011
1010001000100011
1011101111101011
1000100000001311
1111111111111111
1111111111111111

예제 출력

#1 1

코드

package live06._01_미로1;

import java.util.*;
import java.io.*;

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

	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src/live06/_01_미로1/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		for (int tc = 1; tc <= 10; tc++) {
			int tcNum = Integer.parseInt(br.readLine());
			maze = new int[16][16];
			visited = new boolean[16][16];
			answer = 0;

			int startR = 0;
			int startC = 0;

			for (int i = 0; i < 16; i++) {
				String mazeLine = br.readLine();
				for (int j = 0; j < 16; j++) {
					maze[i][j] = mazeLine.charAt(j) - '0';

					if (maze[i][j] == 2) {
						startR = i;
						startC = j;
					}
				}
			}

			bw.write("#" + tcNum + " " + String.valueOf(dfs(startR, startC)) + "\n");
		}

		br.close();
		bw.close();
	}

	static int dfs(int row, int col) {
		if (maze[row][col] == 3) {
			answer = 1;
			return 1;
		}

		visited[row][col] = true;

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

			if (nr < 0 || nr >= 16 || nc < 0 || nc >= 16)
				continue;

			if (maze[nr][nc] == 1)
				continue;

			if (visited[nr][nc])
				continue;

			dfs(nr, nc);
		}

		return answer;
	}
}

풀이

💡 접근 방식

• 시작점 2에서 도착점 3으로 가는 것이 가능한지 판단하는 문제
• 16 x 16 미로
• 현재 위치에서 상하좌우로 값들을 확인하며 다음의 조건들을 구현
  1) 범위는 maze[0][0] ~ maze [15][15]
  2) 확인한 값이 1일 때
  3) 이미 방문한 경로일 때
  4) 확인한 값이 3일 때

💡 미로 정보 및 시작점 저장

int startR = 0;
int startC = 0;

for (int i = 0; i < 16; i++) {
	String mazeLine = br.readLine();
	for (int j = 0; j < 16; j++) {
		maze[i][j] = mazeLine.charAt(j) - '0';

		if (maze[i][j] == 2) {
			startR = i;
			startC = j;
		}
	}
}

• 미로에 대한 정보를 입력받음과 동시에 시작점을 저장한다.

💡 DFS 구현

static int dfs(int row, int col) {
	if (maze[row][col] == 3) {
		answer = 1;
		return 1;
	}
    
	visited[row][col] = true;

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

		if (nr < 0 || nr >= 16 || nc < 0 || nc >= 16)
			continue;

		if (maze[nr][nc] == 1)
			continue;

		if (visited[nr][nc])
			continue;

		dfs(nr, nc);
	}
    
	return answer;
}

• 현재 내 위치를 먼저 확인을 해줘야 불필요한 dfs함수 반복을 가지치기할 수 있습니다.
• 따라서 이동할 위치에 3이 들어있다면 answer = 1을 저장합니다.
• 이 때 주의할 점은 return 1은 해당 재귀가 종료되고 돌아가는 시점에 사용되지 않아 사라지는 값이므로 answer에 1을 꼭 저장해야합니다.
• answer값은 dfs문의 마지막에서 return answer;로 반환하게 됩니다.
• 현재 방문 여부도 visitied[row][col]에 저장합니다.
• for 반복문은 상하좌우를 돌아가기 때문에 0 ~ 3까지 4번 반복합니다.
• 좌표 이동하는 코드는 전역 변수로 설정합니다.
• nr & nc로 이동할 값을 저장합니다.
• 이동할 방향에 대한 조건을 확인합니다.
  • 미로 범위 내에 있는 위치인가?
  • 이동할 위치가 벽인가?
  • 이미 방문했던 위치인가?
• 위의 조건을 하나라도 만족하면 해당 for문을 빠져나옵니다.
  • 만약 i = 0 이라고 한다면 i = 1로 넘어간다는 뜻입니다.
  • 이 때, dfs함수도 건너뛰게 됩니다.
• 하나도 만족하지 않는다면 dfs를 반복하며 다음 위치로 이동하게 됩니다.

💡 continue & break

• continue
  • 현재 반복문을 건너뛰고 다음 반복문으로 넘어갑니다.
• break
  • 반복문 자체를 종료해서 빠져나옵니다.

for (int i = 0; i < 5; i++) {
	if (i == 3) {
    	continue;
    }
    System.out.print(i + " ");
}

// 출력 : 0 1 2 4

for (int i = 0; i < 5; i++) {
	if (i == 3) {
    	break;
    }
    System.out.print(i + " ");
}

// 출력 : 0 1 2