미로 탐색(BFS) - 실버1

- 미로 탐색 문제

https://www.acmicpc.net/problem/2178

 

- 풀이

걸린 시간 : 10~15분

import java.io.*;
import java.util.*;
public class Main {

    public static int N, M;
    public static ArrayList<Integer> count = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        int[][] graph = new int[M][N];
        boolean[][] visited = new boolean[M][N];
        Queue<int[]> q = new LinkedList<>();
        for(int i = 0; i < M; i++){
            String[] str = br.readLine().split("");
            for(int j = 0; j < N; j++){
                graph[i][j] = Integer.parseInt(str[j]);
            }
        }

        q.offer(new int[]{0, 0});
        while(!q.isEmpty()){
            int[] point = q.poll();
            bfs(graph, visited, q, point[0] + 1, point[1], graph[point[0]][point[1]]);
            bfs(graph, visited, q, point[0], point[1] + 1, graph[point[0]][point[1]]);
            bfs(graph, visited, q, point[0] - 1, point[1], graph[point[0]][point[1]]);
            bfs(graph, visited, q, point[0], point[1] - 1, graph[point[0]][point[1]]);
        }

        bw.write(String.valueOf(graph[M-1][N-1]));
        br.close();
        bw.close();
    }

    public static void bfs(int[][] graph, boolean[][] visited, Queue<int[]> q, int y, int x, int before){
        if(y < 0 || y >= M || x < 0 || x >= N){
            return;
        }
        if(visited[y][x]){
            return;
        }
        if(graph[y][x] == 0){
            return;
        }

        visited[y][x] = true;
        graph[y][x] = before + 1;
        q.offer(new int[]{y, x});
    }
}

골드 3 문제를 도전했다가 명존쎄 한대 맞고, 피신한 문제이다.

골드 3 문제를 로직은 다 짰는데, 시간 초과가 나서 포기했다.

줄이기 위해 HashSet등을 이용하라고 하는데, 일단 BFS 적응부터가 먼저라고 생각했다.

그래도 왜안되지, 왜안되지 하다가 알게된건

Queue 안의 요소는 poll() 하고나면 없어지니깐,

2겹의 Queue 반복문에서는, Q에 다시 시작점을 추가해줘야 한다는 것이다.

참 바보같은 실수였다.

 

그래서 일단 쉬운 문제를 찾았고, 실버1 문제가 눈에 들어왔다.

어제 토마토 문제가 좀 어려웠어서 그런지,

이런 문제는 쉽게 느껴진다.

 

골드 3 문제,,, 반드시 풀어서 올리겠습니다.