[SWEA] #1226 미로1

19817 단어 JavaSWEAalgorithmJava

Link

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE


Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Solution {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static class Pos {
        int x;
        int y;
        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int testCase = 1; testCase <= 10; testCase++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), "");
            st.nextToken();
            Queue<Pos> queue = new LinkedList<>();
            Pos end = null;
            int[][] arr = new int[16][16];
            int[][] visited = new int[16][16];
            int flag = 0;
            for (int i = 0; i < 16; i++) {
                st = new StringTokenizer(br.readLine(), "");
                char[] chartoint = st.nextToken().toCharArray();
                for (int j = 0; j < 16; j++) {
                    int temp = Character.getNumericValue(chartoint[j]);
                    arr[i][j] = temp;
                    if (temp == 2) {
                        queue.offer(new Pos(i, j));
                    }
                    else if (temp == 3) {
                        end = new Pos(i, j);
                    }
                }
            }
            while (!queue.isEmpty()) {
                Pos pos = queue.poll();
                int x = pos.x;
                int y = pos.y;
                if (x == end.x && y == end.y) {
                    flag = 1;
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    if ((0 <= x + dx[i] && x + dx[i] < 16 && 0 <= y + dy[i] && y + dy[i] < 16) && arr[x + dx[i]][y + dy[i]] != 1 && visited[x + dx[i]][y + dy[i]] != 1) {
                        visited[x + dx[i]][y + dy[i]] = 1;
                        queue.offer(new Pos(x + dx[i], y + dy[i]));
                    }
                }
            }
            System.out.printf("#%d %d\n", testCase, flag);
        }
    }
}

Solution

좌표를 저장할 내부 클래스 pos를 미리 지정해놓고 arr를 입력받으면서 출발 지점과 도착 지점, visited를 모두 초기화시켜준다.
그리고 큐가 빌때까지 while문을 돌면서 큐에있는 좌표를 꺼내 도착지점이면 flag를 1로 변경후 break, 아니면 다시 for문을 돌면서 dx, dy에 맞는 좌표를 더해 유효한 좌표인지, 방문한적이 없는지, 1이 아닌지를 체크후 모두 true면 visited에 체크를 하고 다시 큐에 넣는다.
while문이 끝나면 flag를 출력시켜준다.

좋은 웹페이지 즐겨찾기