[SWEA]#1226 [S/W 문제해결 기본] 7일차 - 미로1
문제
아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.
가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.
주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.
아래의 예시에서는 도달 가능하다.
아래의 예시에서는 출발점이 (1, 1)이고, 도착점이 (11, 11)이며 도달이 불가능하다.
입력
각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.
총 10개의 테스트케이스가 주어진다.
테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.
출력
#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도달 가능 여부를 1 또는 0으로 표시한다 (1 - 가능함, 0 - 가능하지 않음).
예제 입력 1
1
1111111111111111
1210000000100011
1010101110101111
1000100010100011
1111111010101011
1000000010101011
1011111110111011
1010000010001011
1010101111101011
1010100010001011
1010111010111011
1010001000100011
1011101111101011
1000100000001311
1111111111111111
1111111111111111
2
1111111111111111
1200000010000011
1011111011111011
1000001010000011
1110101010111011
1010101010100011
1011111010111111
1000001010000011
1011101011111011
1010101010000011
1010101010111111
1010100000130011
1010111111111011
1000000000000011
1111111111111111
1111111111111111
...
예제 출력 1
#1 1
#2 1
...
풀이
이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 푸는 가장 일반적인 문제이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
class Solution
{
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String args[]) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = 10;
for(int test_case = 1; test_case <= T; test_case++)
{
br.readLine();
int[][] map = new int[16][16];
int startX = 0;
int startY = 0;
for(int i=0; i<16; i++) {
String input = br.readLine();
for(int j=0; j<16; j++) {
map[i][j] = input.charAt(j) - '0';
if(map[i][j]==2) {
startX = i;
startY = j;
}
}
}
int ans = bfs(map, startX, startY);
System.out.println("#"+test_case+" "+ans);
}
}
public static int bfs(int[][] map, int x, int y) {
Queue<Pair> queue = new LinkedList<>();
boolean[][] visited = new boolean[16][16];
visited[x][y] = true;
queue.add(new Pair(x, y));
while(!queue.isEmpty()) {
Pair temp = queue.poll();
for(int i=0; i<4; i++) {
int nx = temp.x+dx[i];
int ny = temp.y+dy[i];
if(nx<0 || nx>=16 || ny<0 || ny>=16 || visited[nx][ny]) continue;
if(map[nx][ny]==0) {
visited[nx][ny] = true;
queue.add(new Pair(nx, ny));
}
else if(map[nx][ny]==3)
return 1;
}
}
return 0;
}
public static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}
Author And Source
이 문제에 관하여([SWEA]#1226 [S/W 문제해결 기본] 7일차 - 미로1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pss407/SWEA1226-SW-문제해결-기본-7일차-미로1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)