백준 : 9328

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

9328번: 열쇠

얼마나 많은 보물을 찾을수 있는지 찾는 문제이다.

문제는 BFS탐색을하면서 열쇠를 먹을때마다 다시한번더 BFS를 탐색 해야하는 문제이다.

열쇠인 지점을 먹으면 그지점부터 다시 Queue를 초기화 한다음 다시돌린다.

이렇게해서 visit[][] 배열이 더이상 움직일수 없을때까지 돌리면 정답이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class B9328 {
    static int T;
    static int N, M;
    static char map[][];
    static int dy[] = { 1, -1, 0, 0 };
    static int dx[] = { 0, 0, 1, -1 };
 
    static class Sang {
        int y;
        int x;
 
        public Sang(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        T = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= T; t++) {
            String str[] = br.readLine().split(" ");
 
            N = Integer.parseInt(str[0]);
            M = Integer.parseInt(str[1]);
 
            map = new char[N + 2][M + 2];
            char[] c = null;
            for (int i = 0; i <= N + 1; i++) {
                if (i >= 1 && i <= N) {
                    c = br.readLine().toCharArray();
                }
                for (int j = 0; j <= M + 1; j++) {
                    if (i == 0 || i == N + 1 || j == 0 || j == M + 1) {
                        map[i][j] = '.';
                    } else {
                        map[i][j] = c[j - 1];
                    }
                }
            }
 
            boolean visit[][] = new boolean[N+2][M+2];
            boolean check[] = new boolean[30];
 
            c = br.readLine().toCharArray();
    
            if (c[0] != '0') {
                for (int i = 0; i < c.length; i++) {
                    check[c[i] - 'a'] = true;
                }
            }
 
            Queue<Sang> q = new LinkedList<>();
            boolean marking[][] = new boolean[N + 2][M + 2];
            visit[0][0] =true;
            q.add(new Sang(0, 0));
 
            int Answer = 0;
 
            while (!q.isEmpty()) {
                Sang tmp = q.poll();
                if (map[tmp.y][tmp.x] == '$' && !marking[tmp.y][tmp.x]) {
                    Answer++;
                    marking[tmp.y][tmp.x] = true;
                }
 
                for (int d = 0; d < 4; d++) {
                    int ny = tmp.y + dy[d];
                    int nx = tmp.x + dx[d];
 
                    if (ny < 0 || nx < 0 || ny >= N + 2 || nx >= M + 2)
                        continue;
                    if(visit[ny][nx])
                        continue;
                    if (map[ny][nx] == '*')
                        continue;
                    if (map[ny][nx] >= 'A' && map[ny][nx] <= 'Z') {
                        if (check[map[ny][nx] - 'A']) {
                            visit[ny][nx]=true;
                            q.add(new Sang(ny, nx));
                        }
                    } else if (map[ny][nx] >= 'a' && map[ny][nx] <= 'z'&&!check[map[ny][nx] - 'a']) {
 
                        check[map[ny][nx] - 'a'] = true;
                        q = new LinkedList<>();
                        visit = new boolean[N+2][M+2];
                        visit[ny][nx] = true;
                        q.add(new Sang(ny, nx));
                    } else {
                        visit[ny][nx]=true;
                        q.add(new Sang(ny, nx));
                    }
 
                }
            }
 
            System.out.println(Answer);
 
        }
    }
}