SWEA 1227 미로2(JAVA) 😵

문제 링크

SW Expert Academy

문제 설명

2에서 출발해 0만 거치면서 3까지 갈 수 있는 지 없는 지 여부 구하기

입력

각 테스트 케이스의 첫 번째 줄에는 테스트케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.
총 10개의 테스트 케이스가 주어진다.
테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.

출력

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

구조화

bfs로 0만 Queue에 넣어주면서 3을 만나면 가능함을 출력

소스 코드

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

public class Solution {

	static int T, startR, startC, result, N = 100;
	static int[][] map;
	static boolean[][] visited;
	static int[][] way = {{-1,0},{1,0},{0,-1},{0,1}};
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = 10;
		
		for (int t = 1; t <= T; t++) 
		{
			int temp = Integer.parseInt(br.readLine());
			result = 0;
			map = new int[N][N];
			visited = new boolean[N][N];
			for (int i = 0; i < 100; i++) 
			{
				String str = br.readLine();
				for (int j = 0; j < 100; j++) 
				{
					map[i][j] = str.charAt(j)-'0';
					if(map[i][j]==2)
					{
						startR = i;
						startC = j;
					}
				}
			}
			bfs();
			System.out.printf("#%d %d%n",t,result);
		}
	}
	
	private static void bfs() {

		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {startR, startC});
		
		Outer: while(!q.isEmpty())
		{
			int[] cur = q.poll();
			int cr = cur[0];
			int cc = cur[1];
			visited[cr][cc] = true;
			
			for (int i = 0; i < 4; i++) 
			{
				int nr = cr + way[i][0];
				int nc = cc + way[i][1];
				
				if(!isRight(nr, nc)) continue;
				if(visited[nr][nc]) continue;
				if(map[nr][nc]==3)
				{
					result = 1;
					break Outer;
				}
				if(map[nr][nc]==0)
				{
					q.offer(new int[] {nr, nc});
					visited[nr][nc] = true;
				}
			}
		}
	}

	private static boolean isRight(int nr, int nc) {
		return (nr>=0 && nr<N && nc>=0 && nc<N);
	}

}