[모의 SW 역량평가] 탈주범 검거

doiiollo·2020년 6월 7일
0

모의 SW 역량평가

목록 보기
1/1

문제

7 가지의 파이프 모양과 출발지점이 주어졌을 때 일정 시간내에 도달할 수 있는 지점의 개수를 구하는 문제이다.

문제에서 주어진 파이프의 종류는 다음과 같다.

7 가지 파이프 각각 마다 이동할 수 있는 방향과 이전 지점에서 해당 파이프로 도달 가능한지 여부 두 가지를 모두 고려해 주어야 한다.

위의 그림과 같이 3번 파이프와 6번 파이프가 연결되어 있다고 할 때,

3번 파이프에서는 왼쪽 또는 오른쪽 방향으로 이동할 수 있다.

6번 파이프는 오른쪽에서 접근하는 파이프에 대해서는 왼쪽이 뚫려 있으므로 접근가능하고 아래에서 위로 접근하는 파이프에 대해서는 아래가 뚫려 있으므로 접근가능하다.

따라서 위에서 정한 순서대로 위, 오른쪽, 아래, 왼쪽을 0 부터 3 까지 순서를 부여한다고 했을 때 접근하는 파이프에서의 이동방향과 접근하려는 파이프에서의 이동방향은 대칭을 이룸을 알 수 있다.

때문에 이동하려는 방향의 대칭 방향은 (현재 방향 + 2) % 4 로 구할 수 있다.

소스 코드

public class SWEA_1953_탈주범_검거 {
    static StringBuilder sb = new StringBuilder();

    static int n, m, r, c, l;
    static int[][] b;
    // 1번 부터 7번 각각의 파이프에서 이동가능한 방향
    static boolean[][] pi = { 
        {}, 
        { true, true, true, true }, 
        { true, false, true, false },
        { false, true, false, true }, 
        { true, true, false, false }, 
        { false, true, true, false },
        { false, false, true, true }, 
        { true, false, false, true } 
    };
	
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };

    static class Pair {
        int x, y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int bfs() {
        Queue<Pair> q = new LinkedList<>();
        boolean[][] visit = new boolean[n][m];

        int time = 0; // 경과시간
        int cnt = 0;  // 이동할 수 있는 좌표의 개수
        visit[r][c] = true;
        q.add(new Pair(r, c));

        while (!q.isEmpty()) {
            int size = q.size();
            // 제한 시간 전까지 이동할 수 있는 거리를 고려 
            if (time < l)
                cnt += size;
            // 제한시간이 되면 결과 값을 반환하고 탐색을 종료한다.
            if(time == l) return cnt;
            for (int i = 0; i < size; i++) {
                Pair p = q.poll();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = p.x + dx[dir];
                    int ny = p.y + dy[dir];
                    // 현재 파이프에서 해당 방향으로 안열려 있으면 못감
                    if (!pi[b[p.x][p.y]][dir]) continue;
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m || 
                            visit[nx][ny] || b[nx][ny] == 0) continue;
                    // 이동하려는 파이프에서 해당 방향으로 안열려 있으면 못감
                    if (!pi[b[nx][ny]][(dir + 2) % 4]) continue;
                    visit[nx][ny] = true;
                    q.add(new Pair(nx, ny));
                }
            }
            time += 1;
        }
        return cnt;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            sb.append("#").append(t).append(" ");
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()); // 세로
            m = Integer.parseInt(st.nextToken()); // 가로
            r = Integer.parseInt(st.nextToken()); // 출발 지점의 x좌표
            c = Integer.parseInt(st.nextToken()); // 출발 지점의 y좌표
            l = Integer.parseInt(st.nextToken()); // 제한 시간

            b = new int[n][m];
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < m; j++) {
                    b[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int ans = bfs();
            sb.append(ans).append("\n");
        }
        System.out.println(sb);
    }
}

응용

백준 2931 가스관

profile
고수가 되고 싶어요

0개의 댓글