📙[Algo] 24.06.05 알고리즘

알고리즘 문제) BOJ 14890. 경사로

• 링크 : https://www.acmicpc.net/problem/14890

문제 요약

• N*N 지도가 존재
• 길은 한 행, 한 열 전부를 의미
  • 한쪽 끝에서 다른쪽 끝까지 지나가는 것
• 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같을 것
• 또는 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다
  • 경사로 높이는 항상 1, 길이는 L
  • 개수는 무한 개
• 경사로 설치는 다음 조건을 만족할 것
  • 낮은 칸에 놓을 것
  • 경사로를 놓을 낮은 칸의 높이는 모두 같고, L개의 칸이 연속될 것
  • 낮은 칸과 높은 칸의 차이는 1일 것
• 지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성

시간 제한

• 2초

입력

• 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)
• 둘째 줄부터 N개의 줄에 지도
  • 각 칸의 높이는 10보다 작거나 같은 자연수

출력

• 첫째 줄에 지나갈 수 있는 길의 개수를 출력

접근법

• 높이차이가 발생하는 곳에 경사로를 놓을 것
  • abs(arr[i][j] - arr[i][j+1]) > 1 -> 불가능 return 0
  • abs(arr[i][j] - arr[i][j+1]) == 0 -> pass
  • abs(arr[i][j] - arr[i][j+1]) == 1 -> 경사로 놓기
• (1번 충족 가정) 낮은 곳에 경사로 놓기 + L개의 연속된 칸에 놓기(높이 같아야 함)
  • len 변수 -> 높이가 같은 연속된 칸 카운트
  • if 낮은칸 -> 높은칸 만난 경우
    • len변수 그대로 사용
    • if (len < L) -> 불가능 return 0
    • else
      • arr[i][j] ~ arr[i][j-L+1] 까지 경사로 놓을 수 있는지 체크 -
        • rowcheck가 false 여부 체크
      • 가능하면 rowCheck 배열(또는 colCheck)에 같은 범위 true 체크
      • 경사로 놓기가 끝나면 -> arr[i][j+1]부터 다시 카운트 시작
  • if 높은칸 -> 낮은칸 만난 경우
    • len 변수 초기화
    • arr[i][j+1]~arr[i][j+L] 까지 높이가 균일한지 체크
      • • rowCheck false 여부 체크
    • 가능하면 rowCheck 배열(또는 colCheck)에 같은 범위 true 체크

코드

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

// 48분
public class Main {
    static int N, L;
    static int[][] arr;
    static boolean[][] rowCheck;
    static boolean[][] colCheck;

    /*
       1. 높은 곳과 높이 차는 1일 것
       2. 낮은 칸에 경사로를 놓을 것
       3. 경사로를 놓는 L개의 연속된 칸의 높이는 같을 것

       [접근]
       1. 높이차이가 발생하는 곳에 경사로를 놓을 것
          abs(arr[i][j] - arr[i][j+1]) > 1 -> 불가능 return 0
          abs(arr[i][j] - arr[i][j+1]) == 0 -> pass
          abs(arr[i][j] - arr[i][j+1]) == 1 -> 경사로 놓기
       2. (1번 충족 가정) 낮은 곳에 경사로 놓기 + 3. L개의 연속된 칸에 놓기(높이 같아야 함)
          len 변수 -> 높이가 같은 연속된 칸 카운트

          if 낮은칸 -> 높은칸 만난 경우
             len변수 그대로 사용
             if (len < L) -> 불가능 return 0
             else
                arr[i][j] ~ arr[i][j-L+1] 까지 경사로 놓을 수 있는지 체크
                    rowcheck가 false 여부 체크
                가능하면 rowCheck 배열(또는 colCheck)에 같은 범위 true 체크
             경사로 놓기가 끝나면 -> arr[i][j+1]부터 다시 카운트 시작
          if 높은칸 -> 낮은칸 만난 경우
             len 변수 초기화
             arr[i][j+1]~arr[i][j+L] 까지 높이가 균일한지 체크
             + rowCheck false 여부 체크
             가능하면 rowCheck 배열(또는 colCheck)에 같은 범위 true 체크
     */

    static int colRoad(int col) {
        int len = 1, diff;
        for (int row = 0; row < N - 1; row++) {
            diff = arr[row][col] - arr[row + 1][col];

            if (diff == 0) {
                len++;
            } else if (Math.abs(diff) > 1) {
                return 0;
            } else {
                if (diff == -1) {
                    // 낮 -> 높
                    if (len < L) return 0;

                    // 이미 경사로 있는지 체크
                    for (int i = row; i >= row - L + 1; i--) {
                        if (colCheck[i][col]) return 0;
                    }

                    // 경사로 놓기
                    for (int i = row; i >= row - L + 1; i--) {
                        colCheck[i][col] = true;
                    }

                    len = 1;

                } else if (diff == 1) {
                    // 높 -> 낮
                    len = 1;

                    // 낮은 곳 높이 균일한지 체크
                    for (int i = row + 1; i < row + L; i++) {
                        if (i + 1 >= N) return 0;
                        if (arr[i][col] != arr[i + 1][col]) return 0;
                    }

                    // 이미 경사로 있는지 체크
                    for (int i = row + 1; i <= row + L; i++) {
                        if (colCheck[i][col]) return 0;
                    }

                    // 경사로 놓기
                    for (int i = row + 1; i <= row + L; i++) {
                        colCheck[i][col] = true;
                    }
                }
            }
        }

        return 1;
    }
    static int rowRoad(int row) {
        int len = 1, diff;
        for (int col = 0; col < N - 1; col++) {
            diff = arr[row][col] - arr[row][col + 1];

            if (diff == 0) {
                len++;
            } else if (Math.abs(diff) > 1) {
                return 0;
            } else {
                if (diff == -1) {
                    // 낮 -> 높
                    if (len < L) return 0;

                    // 이미 경사로 있는지 체크
                    for (int i = col; i >= col - L + 1; i--) {
                        if (rowCheck[row][i]) return 0;
                    }

                    // 경사로 놓기
                    for (int i = col; i >= col - L + 1; i--) {
                        rowCheck[row][i] = true;
                    }

                    len = 1;

                } else if (diff == 1) {
                    // 높 -> 낮
                    len = 1;

                    // 낮은 곳 높이 균일한지 체크
                    for (int i = col + 1; i < col + L; i++) {
                        if (i + 1 >= N) return 0;
                        if (arr[row][i] != arr[row][i + 1]) return 0;
                    }

                    // 이미 경사로 있는지 체크
                    for (int i = col + 1; i <= col + L; i++) {
                        if (rowCheck[row][i]) return 0;
                    }

                    // 경사로 놓기
                    for (int i = col + 1; i <= col + L; i++) {
                        rowCheck[row][i] = true;
                    }
                }
            }
        }

        return 1;
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

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

        rowCheck = new boolean[N][N];
        colCheck = new boolean[N][N];

        int ans = 0;
        for (int row = 0; row < N; row++) {
            ans += rowRoad(row);
        }

        for (int col = 0; col < N; col++) {
            ans += colRoad(col);
        }

        System.out.println(ans);

        br.close();
    }
}

 

알고리즘 문제) BOJ 13460. 구슬 탈출2

• 링크 : https://www.acmicpc.net/problem/13460

문제 요약

• N*M 크기 보드가 존재
• 가장 바깥 행과 열은 모두 막혀 있으며, 구멍은 하나 존재
• 빨간 구슬과 파란 구슬은 보드의 한 칸씩을 차지하여 들어가 있음
• 해당 보드를 기울여서 중력을 이용해 구슬을 굴릴 수 있다.
  • 이때, 구슬은 동시에 움직인다.
• 목표는 빨간 구슬을 먼저 구멍에서 빼내는 것이다
  • 파란 구슬 먼저 또는 동시에 빠지면 실패
• 구슬은 동시에 같은 칸에 있을 수 없다.
• 동작은 구슬이 더이상 움직이지 않을 때까지 하려고 한다.
• 최소 몇 번 만에 빨간 구슬을 구멍에서 빼낼 수 있을까?

시간 제한

• 2초

입력

• 보드 세로, 가로 크기 N, M
  • 3 ≤ N, M ≤ 10
• N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다.
  • . : 빈 칸

  • : 장애물 또는 벽

  • O : 구멍
  • R : 빨간 구슬 위치
  • B : 파란 구슬 위치

출력

• 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력
  • 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력

접근법

• 총 4방향으로 굴릴 수 있음
  • 어떤 방향으로 굴렀느냐에 따라 경우가 여러 케이스 생김
• 최소 횟수를 구하므로 bfs 알고리즘 사용
  • 큐에 빨간 구슬 좌표, 파란 구슬 좌표 저장
  • 방문 체크 -> 4차원 배열 사용(빨간 구슬 좌표, 파란 구슬 좌표)

코드

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

// 45분
public class Main {
    static int N, M;
    static char[][] arr;
    static boolean[][][][] visited;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static int redRow, redCol, blueRow, blueCol;

    /*
       [접근]
       ** 게임이 끝나는 경우
          - 구슬이 더이상 움직이지 않을 때
          - 구멍에 구슬이 빠져 나갈 때 -> 파란 구슬이 먼저 꺼내지면 X


       총 4방향으로 굴릴 수 있음
       어떤 방향으로 굴렀느냐에 따라 경우가 여러 케이스 생김
       최소 횟수를 구하므로 bfs 알고리즘 사용 -> 큐에 빨간 구슬 좌표, 파란 구슬 좌표 저장
       방문 체크 -> 4차원 배열 사용(빨간 구슬 좌표, 파란 구슬 좌표)
     */

    static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{redRow, redCol, blueRow, blueCol});
        visited[redRow][redCol][blueRow][blueCol] = true;

        int size, count = 0;
        int crRow, crCol, cbRow, cbCol;
        int mrRow, mrCol, mbRow, mbCol;
        boolean redNotFirst, blueNotFirst, isAble;
        while (!q.isEmpty()) {
            size = q.size();

            for (int s = 0; s < size; s++) {
                crRow = q.peek()[0];
                crCol = q.peek()[1];
                cbRow = q.peek()[2];
                cbCol = q.poll()[3];

                if (arr[crRow][crCol] == 'O') return count;

                for (int dir = 0; dir < 4; dir++) {
                    mrRow = crRow;
                    mrCol = crCol;
                    mbRow = cbRow;
                    mbCol = cbCol;
                    redNotFirst = false;
                    blueNotFirst = false;
                    isAble = true;

                    // 빨간 구슬 구르기
                    while (true) {
                        mrRow += delR[dir];
                        mrCol += delC[dir];

                        // 만약 진행 방향쪽에 파란 구슬이 있다면
                        if (mrRow == cbRow && mrCol == cbCol) redNotFirst = true;

                        if (arr[mrRow][mrCol] == 'O') {
                            // 파란 구슬 먼저 구멍을 만난다면
                            if (redNotFirst) {
                                isAble = false;
                            }
                            break;
                        }

                        // 벽이나 장애물을 만난다면
                        if (arr[mrRow][mrCol] == '#') {
                            if (!redNotFirst) {
                                // 빨간 구슬이 먼저 부딪힌 경우
                                mrRow -= delR[dir];
                                mrCol -= delC[dir];
                            } else {
                                // 파란 구슬이 먼저 부딪힌 경우
                                mrRow -= (delR[dir] * 2);
                                mrCol -= (delC[dir] * 2);
                            }
                            break;
                        }
                    }

                    // 파란 구슬 구르기
                    while (true) {
                        mbRow += delR[dir];
                        mbCol += delC[dir];

                        // 만약 진행 방향쪽에 빨간 구슬이 있다면
                        if (mbRow == crRow && mbCol == crCol) blueNotFirst = true;

                        if (arr[mbRow][mbCol] == 'O') {
                            // 파란 구슬도구멍을 만난다면
                            isAble = false;
                            break;
                        }

                        // 벽이나 장애물을 만난다면
                        if (arr[mbRow][mbCol] == '#') {
                            if (!blueNotFirst) {
                                // 파란 구슬이 먼저 부딪힌 경우
                                mbRow -= delR[dir];
                                mbCol -= delC[dir];
                            } else {
                                // 빨간 구슬이 먼저 부딪힌 경우
                                mbRow -= (delR[dir] * 2);
                                mbCol -= (delC[dir] * 2);
                            }
                            break;
                        }
                    }

                    // 파란구슬이 먼저 또는 동시에 구멍에 빠진 경우
                    if (!isAble) continue;

                    if (visited[mrRow][mrCol][mbRow][mbCol]) continue;

                    visited[mrRow][mrCol][mbRow][mbCol] = true;
                    q.add(new int[]{mrRow, mrCol, mbRow, mbCol});
                }
            }

            if (++count > 10) break;
        }


        return -1;
    }


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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new char[N][M];
        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = input.charAt(j);

                if (arr[i][j] == 'R') {
                    redRow = i;
                    redCol = j;
                } else if (arr[i][j] == 'B') {
                    blueRow = i;
                    blueCol = j;
                }
            }
        }

        visited = new boolean[N][M][N][M];

        System.out.println(bfs());

        br.close();
    }
}