📙[Algo] 24.07.08 알고리즘

알고리즘 문제) BOJ 4179. 불!

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

문제 요약

• 지훈이가 불에서 타기 전에 얼마나 빨리 탈출할 수 있는지 판단하기
• 불은 매 분마다 한칸씩 수평, 수직으로 이동(네방향 확산)
• 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다
• 지훈이와 불은 벽을 통과할 수 없다

시간 제한

• 1초

입력

• R C
  • 1 ≤ R,C ≤ 1000
  • 행, 열
• R개의 줄에 맵이 주어짐
  • ‘#’ : 벽
  • ‘.’ : 빈칸
  • ‘J’ : 지훈이 초기 위치
  • ‘F’ : 블이 난 공간
  • J는 입력에서 하나만 주어진다.

출력

• 지훈이가 미로를 탈출 할 수 없다면 IMPOSSIBLE
• 가능하다면, 가장 빠른 탈출 시간 출력

접근법

• bfs 알고리즘 사용
• 우선 지훈이가 이동 가능한 경우는 여러 케이스가 있다
  • 큐에 bfs를 돌며 이동하가능한 좌표들을 담아준다.
  • 이때, 큐에 있는 좌표 개수만큼만 돌아야한다.
  • 여기서, 큐에서 꺼낸 좌표가 이미 불이 퍼진 자리라면, 애초에 지훈이가 이동이 불가능한 곳이었다 판단해서 따로 이동하지 않고 넘긴다.
  • 만약 이동한 위치가 경계 밖이라면 탈출했다고 판단하고 return 1을 해준다.
• 그 다음, 불을 퍼뜨리는데,
  • 이때도 bfs알고리즘으로 큐에 있는 좌표 개수만큼만 돌렸다.
  • 퍼뜨리면서 map정보를 FIRE값으로 갱신
• while문을 돌며, 1분마다 지훈이 이동 & 불 퍼뜨리기를 하는데,
  • 지훈이 이동 moveJihoon()값이 1이면 탈출을 한 것이므로 while문을 빠져나간다.
  • 그러나, 지훈이가 이동하고 나서 지훈이 좌표를 담은 큐 사이즈가 0일 경우에는, 이동가능한 좌표가 없다는 뜻으로 판단하고 String 변수에 IMPOSSIBLE 저장 후 while문을 빠져나간다.

코드

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

public class Main {
    static int R, C;
    static int[][] map;
    static final int FIRE = 1;
    static final int EMPTY = 0;
    static final int WALL = 2;
    static Queue<int[]> fire = new LinkedList<>();
    static Queue<int[]> jihoon = new LinkedList<>();
    static boolean[][] visitedFire;
    static boolean[][] visitedJihoon;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};

    static void spreadFire() {
        int cr, cc, mr, mc, size;
        while (!fire.isEmpty()) {
            size = fire.size();

            for (int s = 0; s < size; s++) {
                cr = fire.peek()[0];
                cc = fire.poll()[1];

                for (int dir = 0; dir < 4; dir++) {
                    mr = cr + delR[dir];
                    mc = cc + delC[dir];

                    if (mr < 0 || mc < 0 || R <= mr || C <= mc
                            || visitedFire[mr][mc] || map[mr][mc] == WALL) continue;

                    map[mr][mc] = FIRE;
                    visitedFire[mr][mc] = true;
                    fire.offer(new int[]{mr, mc});
                }
            }
            return;
        }
    }

    static int moveJihoon() {
        int cr, cc, mr, mc, size;
        while (!jihoon.isEmpty()) {
            size = jihoon.size();

            for (int s = 0; s < size; s++) {
                cr = jihoon.peek()[0];
                cc = jihoon.poll()[1];

                if (map[cr][cc] == FIRE) continue;

                for (int dir = 0; dir < 4; dir++) {
                    mr = cr + delR[dir];
                    mc = cc + delC[dir];

                    // 탈출 성공
                    if (mr < 0 || mc < 0 || R <= mr || C <= mc) return 1;

                    if (visitedJihoon[mr][mc] || map[mr][mc] == WALL || map[mr][mc] == FIRE) continue;

                    visitedJihoon[mr][mc] = true;
                    jihoon.offer(new int[]{mr, mc});
                }
            }

            return 0;
        }

        return 0;
    }



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

        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new int[R][C];
        visitedFire = new boolean[R][C];
        visitedJihoon = new boolean[R][C];
        String input; char c;
        for (int i = 0; i < R; i++) {
            input = br.readLine();
            for (int j = 0; j < C; j++) {
                c = input.charAt(j);
                if (c == '#') map[i][j] = WALL;
                else if (c == '.') map[i][j] = EMPTY;
                else if (c == 'J') {
                    map[i][j] = EMPTY;
                    jihoon.offer(new int[]{i, j});
                } else {
                    map[i][j] = FIRE;
                    visitedFire[i][j] = true;
                    fire.offer(new int[]{i, j});
                }
            }
        }

        int minute = 1;
        String ans = "";
        while (true) {
            // 지훈이 이동
            if (moveJihoon() == 1) break;

            // jihoon이가 이동가능한 좌표가 없다는 거는 지훈이가 이동 가능한 자리가 모든 불이 퍼진 자리라는 뜻
            // 따라서 탈출 불가능
            if (jihoon.isEmpty()){
                ans = "IMPOSSIBLE";
                break;
            }

            // 불퍼뜨리기
            spreadFire();

            minute++;
        }

        if (ans.equals("IMPOSSIBLE")) System.out.println(ans);
        else System.out.println(minute);

    }
}

 

알고리즘 문제) BOJ 1765. 닭싸움 팀 정하기

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

문제 요약

• 닭싸움 팀을 정하려고한다.
• 이때 인간관계를 다음과 같이 정의
  • 내 친구의 친구도 친구
  • 내 원수의 원수도 친구
• 이때, 두 학생이 친구면 같은 팀이며, 같은 팀은 모두 친구
• 인간관계가 주어졌을 때, 최대 얼마나 많은 팀을 만들 수 있는지 구해라

시간 제한

• 2초

입력

• 학생 수 n
  • 2 ≤ n ≤ 1000
• 인간관계 수 m
  • 1 ≤ m ≤ 5000
• m개의 줄에 학생 간 인간관계가 주어짐
  • F p q : p와 q가 친구
  • E p q : p와 q는 원수
  • 1 ≤ p < q ≤ n
• 입력에 모순은 없다(동시에 원수이며 친구 X)

출력

• 가능한 최대 팀 개수?

접근법

• Union & Find 사용
• 만약 a와 b가 친구라면
  • union을 통해 같은 집합으로 묶어주었다.
• 만약 a와 b가 원수라면
  • 원수 관계를 담는 리스트배열 lstE[a].add(b), lstE[b].add(a) 업데이트
  • 원수의 원수도 친구이므로
    • lstE[a]와 lstE[b]에 추가된 값들을 순회하며,
      • lstE[a]의 값들과 b, lstE[b]의 값들과 union으로 같은 집합으로 묶는다.
• 마지막으로 set을 이용해 team 배열을 순회하며 부모노드를 찾아 답아주고, set의 크기를 출력 → 같은 부모는 같은 팀이므로, set의크기가 곧 팀의 개수가 된다.

코드

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

public class Main {
    static int N, M;
    static int[] team;
    static ArrayList<Integer>[] lstE;

    static int find(int x) {
        if (team[x] == x) return x;

        team[x] = find(team[x]);
        return team[x];
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        team[b] = a;
    }

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

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        team = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            team[i] = i;
        }

        lstE = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            lstE[i] = new ArrayList<>();
        }

        String r;
        int a, b, c;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            r = st.nextToken();

            if (r.equals("E")) {
                // 원수 관계
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());
                lstE[a].add(b);
                lstE[b].add(a);

                for (int j = 0; j < lstE[b].size(); j++) {
                    c = lstE[b].get(j);
                    if (find(a) == find(c)) continue;
                    union(a, c);
                }

                for (int j = 0; j < lstE[a].size(); j++) {
                    c = lstE[a].get(j);
                    if (find(b) == find(c)) continue;
                    union(b, c);
                }
            } else {
                // 친구 관계
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());
                if (find(a) == find(b)) continue;
                union(a, b);
            }
        }

        Set<Integer> tCnt = new TreeSet<>();
        for (int i = 1; i < N + 1; i++) {
            tCnt.add(find(i));
        }

        System.out.println(tCnt.size());
    }
}

 

알고리즘 문제) BOJ 30464. 시간낭비

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

문제 요약

• 등굣길은 N개의 칸이 가로로 놓인 형태
• 각 칸은 왼쪽 칸부터 오른쪽으로 1~N까지 번호가 매겨져 있다
• 이때, 건덕이는 1번 칸, 학교는 N번 칸에 위치
• 건덕이는 학교를 바라보는 방향으로 서있으며, 1분마다 현재 칸에 쓰인 수만큼 해당 방향으로 이동한다.
  • 이때, 등굣길을 벗어나도록 이동 불가능
• 건덕이는 바라보는 방향을 최대 두번 반전할 수 있다.
• 이때, 학교에 도착하는 시간을 최대한 늦출경우 걸리는 시간은??

시간 제한

• 1초

입력

• 학교가 있는 칸의 번호 N
  • 3 ≤ N ≤ 20만
• 각 칸에 쓰인 정수 ai가 공백을 두고 주어짐
  • 0 ≤ ai ≤ 20만

출력

• 건덕이가 최대한 시간을 끈 뒤, 학교가 있는 칸에 처음으로 도착하는 시간을 출력
  • 도착할 수 없다면 -1출력

접근법

• 풀이 맞는 거 같은데 왜 틀리지???라고 생각된다면… 문제를 잘 읽어보자..
  • 칸에 들어올 수 있는 값은 0도 있다…
    • 그렇기 때문에 도착지 제외하고 중간에 0을 밟았을 경우 오도가도 못하니까 불가능한 경우라고 판단하고 가지치기 해야한다…
• 탑다운DP로 풀었따
  • 현재 위치를 cur 변수, 역전 여부를 reverse 변수에 담았다
  • 만약 reverse가 1이면 반대 방향, 그게 아닐 경우 정방향이라 판단했다
  • reverse개수가 1이하일 경우, 방향을 바꾼 경우도 호출
    • 이때 현재 방향의 반대방향으로 이동시키고 reverse + 1
  • 경계를 벗어난 경우, 혹은 도착지를 제외하고 현재 칸의 숫자가 0인경우는 최솟값을 반환시켜 가지치키
  • 기저조건은 도착지에 도착한 경우

코드

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

public class Main {
    static int N;
    static int[] arr;
    static int[][] dp;

    static int recur(int cur, int reverse) {

        if (cur < 0 || N <= cur) return Integer.MIN_VALUE;

        if (cur == N - 1) return 0;

        if (arr[cur] == 0) return Integer.MIN_VALUE;

        if (dp[cur][reverse] != -1) return dp[cur][reverse];

        int ret = Integer.MIN_VALUE;
        if (reverse == 0) {
            // 정방향으로 이동
            // 또는 방향 바꾸고 반대 방향 이동
            ret = Math.max(recur(cur - arr[cur], reverse + 1) + 1
                    , recur(cur + arr[cur], reverse) + 1);
        } else if (reverse == 1) {
            // 반대 방향으로 이동
            // 또는 방향 바꾸고 정방향 이동
            ret = Math.max(recur(cur + arr[cur], reverse + 1) + 1
                    , recur(cur - arr[cur], reverse) + 1);
        } else {
            // 정방향 이동
            ret = Math.max(ret, recur(cur + arr[cur], reverse) + 1);
        }

        dp[cur][reverse] = ret;
        return ret;
    }

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

        N = Integer.parseInt(br.readLine());

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

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

        int ans = recur(0, 0);

        if (ans < 0) System.out.println("-1");
        else System.out.println(ans);
    }
}