📙[Algo] 24.05.02 알고리즘

알고리즘 문제) BOJ 17090. 미로 탈출하기

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

문제 요약

• N*M 미로가 존재
• 크기가 1*1인 칸으로 나누어져 있다.
• 각 칸에 적힌 문자에 따라 이동 가능
  • U : (r-1, c)
  • R : (r, c+1)
  • D : (r+1, c)
  • L : (r, c-1)
• 이때 미로에서 탈출 가능한 큰 계산하기
  • 탈출 가능한 칸 : 미로의 경계 밖으로 이동하게 되는 칸

시간 제한

• 1초

입력

• 미로의 크기 N, M
  • 3 ≤ N, M ≤ 500
• 둘째 줄부터 N개의 줄에 미로에 적힌 문자들이 주어짐

출력

• 탈출 가능한 칸의 수는?

접근법

• 이동하면서 경계를 벗어난 경우를 카운트하면 된다.
• 먼저 백트랙킹으로 구현했을 때
  • 기저 조건으로 경계를 벗어난 경우 return 1;을 해주었다.
  • 또한 무한 루프에 빠지는 구간이 있을 수 있는데, 이를 방지하고자 또 방문한 경우에는 탈출할 수 없다고 판단하여 return 0;을 했다.
  • 또한 출발지마다 재귀를 돌려서 각각의 칸이 탈출할 수 있는 칸인지 파악하고자 했다. → 출발지마다 결과값이 0 또는 1일테니 정답에 반환값을 더해주었다.
• 그다음 같은 곳을 또 재귀로 돌지 않도록, dp배열에 메모이제이션을 했다.

코드

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

public class Main {
    static int N, M;
    static char[][] map;
    static boolean[][] visited;
    static int[][] dp;


    static boolean check(int row, int col) {
        return 1 <= row && 1 <= col && row <= N && col <= M;
    }

    static int backtracking(int row, int col) {

        // 경계를 벗어나면 return 1
        if (!check(row,col)) return 1;

        // 이미 방문한 곳을 또 방문하면 return 0 -> 무한루프 방지
        if (visited[row][col]) return 0;

        // 방문 체크
        visited[row][col] = true;

        // 이미 메모되어 있는 경우에는 기록된거 가져오기
        if (dp[row][col] != -1){
            // 방문 체크 해제 -> 복원
            visited[row][col] = false;
            return dp[row][col];
        }

        // 이동
        int mrow = row, mcol = col;
        if (map[row][col] == 'U')  mrow--;
        else if (map[row][col] == 'R') mcol++;
        else if (map[row][col] == 'D') mrow++;
        else mcol--;

        // 재귀 결과값 담기 (1이면 탈출한 거)
        int ret = backtracking(mrow, mcol);

        // 방문 체크 해제 -> 복원
        visited[row][col] = false;

        // 기록
        dp[row][col] = ret;
        return dp[row][col];
    }

    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;

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

        map = new char[N + 1][M + 1];
        String input;
        for (int i = 1; i <= N; i++) {
            input = br.readLine();

            for (int j = 1; j <= M; j++) {
                map[i][j] = input.charAt(j - 1);
            }
        }

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

        dp = new int[N + 10][M + 10];
        for (int[] ints : dp) {
            Arrays.fill(ints, -1);
        }

        int answer = 0;
        int tmp;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                // 출발지마다 돌리기..
                answer += backtracking(i, j);
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 4811. 알약

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

문제 요약

• 약이 N개 담긴 병이 있음
• 약을 반으로 쪼개서 한 조각을 먹고 다른 조각은 다시 병에 넣는다
  • 만약 꺼냈을 때 반 조각이라면 그냥 먹고, 아니라면 반을 쪼개서 한 조각 먹고, 다시 병에 넣는다.
• 이때 꺼낸 약이 한 조각일 때는 W, 반 조각일 때는 H를 보낸다.
• 가능한 서로 다른 문자열의 개수는?

시간 제한

• 1초

입력

• 입력은 최대 1000개의 테케
  • 각 테케는 한 줄이며 병에 들어있는 약의 수 N이 주어진다
    • N ≤ 30
• 입력의 마지막 줄에는 0이 주어짐

출력

• 각 테케에서 가능한 문자열 개수 출력

접근법

• N = 2 일때, 나올 수 있는 문자열
  • WBWB
  • WWBB
• N = 3 일때, 나올 수 있는 문자열
  • WBWBWB
  • WWBBWB
  • WBWWBB
  • WWBWBB
  • WWWBBB
• 가지치기(조건)
  ⇒ 각 문자는 N개만큼 등장해야한다.(그보다 많거나 적게 X)
  ⇒ B는 앞에 W개수만큼 등장할 수 있다
• 백트랙킹
  • recur(int wcnt, int bcnt)
    • if (wcnt < bcnt || wCnt > N) return 0; → 가지치기
    • if (wcnt + bcnt == 2N) return 1; → 기저조건(문자열길이가 2N개가 될 때 종료)

코드

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

public class Main {
    static int N;
    static long[][] dp = new long[100][100];

    static long recur(int wCnt, int bCnt) {
        if (wCnt < bCnt || wCnt > N) return 0;

        if (wCnt + bCnt == 2 * N) return 1;

        if (dp[wCnt][bCnt] != -1) return dp[wCnt][bCnt];

        long ret = 0;
        ret += recur(wCnt + 1, bCnt);
        ret += recur(wCnt, bCnt + 1);

        dp[wCnt][bCnt] = ret;
        return dp[wCnt][bCnt];
    }

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

        StringBuilder sb = new StringBuilder();
        while (true) {
            N = Integer.parseInt(br.readLine());

            if (N == 0) break;

            for (long[] ints : dp) {
                Arrays.fill(ints, -1);
            }

            sb.append(recur(0, 0)).append("\n");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}