📙[Algo] 24.03.29~24.03.31 알고리즘

알고리즘 문제) BOJ 1967. 숨바꼭질

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

문제 요약

• 시작 점 i에서 1초 후 (1) i - 1, i + 1 이동 가능, (2) i * 2로 이동 가능 할 때 도착 지점 까지 가려면 최소 몇 번 이동?

시간 제한

• 2초

입력

• 시작 위치 N과 도 위치 K
  • N(0 ≤ N ≤ 100,000)
  • K(0 ≤ K ≤ 100,000)

출력

• 도착 지점까지 가려면 최소 몇 번 이동?

코드

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

public class Main {
    static int N, K;
    static boolean[] visited;
    static Queue<Integer> q = new LinkedList<>();
    static int dist;
    static int[] mul = {1, 1, 2};
    static int[] add = {-1, 1, 0};

    static void bfs(int node) {
        q.offer(node);
        visited[node] = true;

        int cur, nxt, size;
        while (!q.isEmpty()) {
            size = q.size();

            for (int i = 0; i < size; i++) {
                cur = q.poll();

                if (cur == K) {
                    System.out.println(dist);
                    return;
                }

                /*
                if (0 <= cur - 1 && !visited[cur - 1]) {

                }

                if (cur + 1 <= 100000 && !visited[cur + 1]) {
                    q.offer(cur + 1);
                    visited[cur + 1] = true;
                }

                if (2 * cur <= 100000 && !visited[2 * cur]) {
                    q.offer(2 * cur);
                    visited[2 * cur] = true;
                }

                연산이 많아지면 번거로우니까 형태를 맞춰준다.
                1 * cur - 1
                1 * cur + 1
                2 * cur + 0

                곱해지는 수, 더해지는 수를 배열로 만들고 활용
                int[] mul = {1, 1, 2};
                int[] add = {-1, 1, 0};
                */

                for (int j = 0; j < 3; j++) {
                    nxt = mul[j] * cur + add[j];

                    if (nxt < 0 || 500000 < nxt || visited[nxt]) continue;

                    q.offer(nxt);
                    visited[nxt] = true;
                }

            }
            dist++;
        }
    }

    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());
        K = Integer.parseInt(st.nextToken());

        visited = new boolean[500010];

        bfs(N);
    }
}

 

알고리즘 문제) BOJ 2178. 미로 탐색

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

문제 요약

• N*M 크기 미로가 있음
• 미로에서 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸
• (1,1)에서 (N,M)위치로 이동할 때 지나야 하는 최소 칸 수 구하기
  • 서로 인접한 칸으로만 이동 가능

시간 제한

• 1초

입력

• 첫째 줄 : 두 정수 N, M
  • 2≤N,M≤100
• N개의 줄에 M개의 정수로 미로가 주어짐(공백X)

출력

• 지나야 하는 최소 칸 수 출력
  • 무조건 도착지로 이동하는 경우만 입력으로 주어짐

코드

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

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static int dist;

    static void bfs(int row, int col) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{row, col});
        visited[row][col] = true;

        int cRow, cCol, mRow, mCol, size;
        while (!q.isEmpty()) {

            size = q.size();

            for (int i = 0; i < size; i++) {
                cRow = q.peek()[0];
                cCol = q.poll()[1];

                if (cRow == N - 1 && cCol == M - 1) return;

                for (int dir = 0; dir < 4; dir++) {
                    mRow = cRow + delR[dir];
                    mCol = cCol + delC[dir];

                    if (mRow < 0 || mCol < 0 || N <= mRow || M <= mCol
                            || visited[mRow][mCol] || map[mRow][mCol] == 0) continue;

                    q.offer(new int[]{mRow, mCol});
                    visited[mRow][mCol] = true;
                }
            }

            dist++;
        }

    }

    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 int[N][M];
        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }

        visited = new boolean[N][M];

        bfs(0, 0);

        bw.write(String.valueOf(dist + 1));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1753. 최단경로

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

문제 요약

• 방향 그래프가 주어지고, 다른 모든 정점으로의 최단 경로 구하기
• 모든 간선의 가중치는 10이하 자연수

시간 제한

• 1초

입력

• 첫째 줄 : 정점 개수 V, 간선 개수 E
  • 1≤V≤2만
  • 1≤E≤30만
• 둘째 줄 : 시작 정점의 번호 K
  • 1≤K≤V
• 셋째 줄부터 E개 줄에 걸쳐 세 개의 정수 u v w가 주어짐
  • u에서 v로가는 가중치 w인 간선이 존재
    • u≠v, w는 10이하 자연수
  • 서로 다른 두 정점 사이에 여러 간선이 존재할 수 있음

출력

• V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값 출력
  • 시작점 자신은 0으로 출력
  • 경로가 존재하지 않은 경우 INF를 출력

접근법

• 다익스트라 알고리즘 사용
• 두 간선 사이 여러 경로가 존재 → 우선순위큐 사용하면 가장 작은 애를 꺼내줌

코드

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

public class Main {
    static int V, E, K;
    static ArrayList<Node>[] list;
    static boolean[] visited;
    static int[] dist;

    static class Node implements Comparable<Node> {
        int to;
        int weight;

        Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }

    static void dijk(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, dist[0]));

        int cur, nxt, nw;
        while (!pq.isEmpty()) {
            cur = pq.poll().to;

            if (visited[cur]) continue;

            visited[cur] = true;

            for (Node node : list[cur]) {
                nxt = node.to;
                nw = dist[cur] + node.weight;

                dist[nxt] = Math.min(dist[nxt], nw);
                pq.offer(new Node(nxt, dist[nxt]));
            }
        }
    }

    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());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

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

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

        int v1, v2, w;
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            // 방향 그래프이니까 하나만
            list[v1].add(new Node(v2, w));
        }

        dist = new int[V + 1];
        Arrays.fill(dist, 300010);
        dist[K] = 0;

        visited = new boolean[V + 1];

        dijk(K);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            if (dist[i] == 300010) sb.append("INF\\n");
            else sb.append(dist[i]+"\\n");
        }

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

 

알고리즘 문제) BOJ 2589. 보물섬

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

문제 요약

• 각 칸은 L(육지), W(바다)로 표시
• 상하좌우로 이동 가능
• 한 칸 이동할 때 1시간
• 보물은 서로 최단 거리로 이동할 때 가장 긴 시간이 걸리는 육지 두 곳에 묻혀 있음
• 보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성

시간 제한

• 1초

입력

• 첫째 줄 : 지도 세로, 가로 크기
  • 각각 50이하
• 둘째 줄부터 지도가 주어짐

출력

• 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력

접근법

최단거리 → bfs

지도 크기가 최대 50*50 이니까 2500

육지인 노드 하나씩 bfs돌리면서 가장 거리가 먼 육지 노드까지 길이를 구한다 ⇒ 이때 최댓값으로 갱신

코드

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

public class Main {
    static int N, M;
    static char[][] map;
    static boolean[][] visited;
    static Queue<int[]> q = new LinkedList<>();
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static int answer;

    static void bfs(int row, int col) {
        q.offer(new int[]{row, col});
        visited[row][col] = true;

        int cRow, cCol, mRow, mCol, size, dist = 0;
        while (!q.isEmpty()) {
            size = q.size();

            for (int i = 0; i < size; i++) {
                cRow = q.peek()[0];
                cCol = q.poll()[1];

                for (int dir = 0; dir < 4; dir++) {
                    mRow = cRow + delR[dir];
                    mCol = cCol + delC[dir];

                    if (mRow < 0 || mCol < 0 || N <= mRow || M <= mCol
                            || visited[mRow][mCol] || map[mRow][mCol] == 'W') continue;

                    q.offer(new int[]{mRow, mCol});
                    visited[mRow][mCol] = true;
                }
            }

            dist++;
        }

        answer = Math.max(answer, dist - 1);

    }

    static void initVisited() {
        for (int i = 0; i < N; i++) {
            Arrays.fill(visited[i], false);
        }
    }

    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][M];
        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 'L') {
                    initVisited();
                    bfs(i, j);
                }
            }
        }

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

 

알고리즘 문제) BOJ 13913. 숨바꼭질 4

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

문제 요약

• 수빈이는 현재 점 N에 위치, 동생은 점 K에 위치
• 수빈이가 현재 위치가 X라면 1초 후에 X-1, X+1, 2*X위치로 이동 가능
• 수빈이와 동생위치가 주어졌을 때 동생을 찾을 수 있는 가장 빠른 시간은?

시간 제한

• 2초

입력

• 수빈이가 있는 위치 N, 동생이 있는 위치 K가 주어짐
  • N(0 ≤ N ≤ 100,000)
  • K(0 ≤ K ≤ 100,000)

출력

• 수빈이가 동생을 찾는 가장 빠른 시간 출력
• 어떻게 이동해야 하는지 공백으로 구분해 출력

접근법

• 경로 기록하기
  • 5 → 6 , 4, 10
  • 4 → 3, 8
  • 8 → 16
  • 16 → 17
  • 방향 그래프를 만든다 생각하면?
    • arr[5][6] = 1, arr[5][4] = 1, ….. arr[16][17] = 1
  • 나중에 경로를 찾을 때 → stack에 담는다 (LIFO)
    int end = 17;
    while(true){
      if (end == 5) stack.add(i);break;
      for (int i=0 ; i≤100000 ≤ i++)
         if(arr[i][end] == 1){
            stack.add(i);   
            end = i;
            break;
         } 
      }
    }
    ⇒ 이렇게하면 메모리 초과
    그냥 그전 노드가 누구였는지 기록 하기

코드

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

public class Main {
    static int N, K;
    static boolean[] visited;
    static int[] mul = {1, 1, 2};
    static int[] add = {1, -1, 0};
    static int[] log;
    static int dist;

    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;

        int cur, nxt, size;
        while (!q.isEmpty()) {

            size = q.size();

            for (int i = 0; i < size; i++) {
                cur = q.poll();

                if (cur == K) return;

                // 1*cur+1
                // 1*cur-1
                // 2*cur+0
                for (int j = 0; j < 3; j++) {
                    nxt = mul[j] * cur + add[j];

                    if (**nxt < 0 || 200000 < nxt** || visited[nxt] ) continue;

                    q.offer(nxt);
                    visited[nxt] = true;
                    log[nxt] = cur;
                }
            }

            dist++;
        }
    }

    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());
        K = Integer.parseInt(st.nextToken());

        visited = new boolean[200010];

        log = new int[200010];

        bfs(N);

        Stack<Integer> stack = new Stack<>();
        int end = K;
        while (true) {
            stack.add(end);

            if (end == N) break;

            end = log[end];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0, size = stack.size(); i < size; i++) {
            sb.append(stack.pop() + " ");
        }

        bw.write(dist + "\\n" + sb);
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 7576. 토마토

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

문제 요약

• M*N
• 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다
  • 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향
• 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수

시간 제한

• 1초

입력

• M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다.
  • 단, 2 ≤ M,N ≤ 1,000
• 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다
  • 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸

출력

• 토마토가 모두 익을 때까지의 최소 날짜를 출력
  • 토마토가 모두 익지는 못하는 상황이면 -1을 출력

코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[][] map;
    static Queue<int[]> q = new LinkedList<>();
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static boolean[][] visited;
    static int tomatoCnt;
    static int cnt;
    static int answer;

    static void bfs() {
        int crow, ccol, mrow, mcol, size;
        while (!q.isEmpty()) {
            size = q.size();

            for (int i = 0; i < size; i++) {
                crow = q.peek()[0];
                ccol = q.poll()[1];

                cnt++;

                for (int dir = 0; dir < 4; dir++) {
                    mrow = crow + delR[dir];
                    mcol = ccol + delC[dir];

                    if (mrow < 0 || mcol < 0 || N <= mrow || M <= mcol
                            || visited[mrow][mcol] || map[mrow][mcol] == -1) continue;

                    visited[mrow][mcol] = true;
                    q.offer(new int[]{mrow, mcol});
                }
            }

            answer++;
        }
    }

    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());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

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

                if (map[i][j] != -1){
                    tomatoCnt++;

                    if (map[i][j] == 1){
                        q.offer(new int[]{i, j});
                        visited[i][j] = true;
                    }
                }
            }
        }

        bfs();

        if (cnt == tomatoCnt) bw.write(String.valueOf(answer - 1));
        else bw.write(String.valueOf(-1));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1261. 알고스팟

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

문제 요약

• 미로는 NM 크기이며, 총 11 크기 방으로 이루어져 있다
• 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)
• 여러 명이 다른 방에 있을 수는 없다.
• 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지

시간 제한

• 1초

입력

• 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)
• 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1
  • 0은 빈 방을 의미하고, 1은 벽
  • (1, 1)과 (N, M)은 항상 뚫려있다.

출력

• 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력

코드

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[][] map;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static boolean[][] visited;

    static class Node implements Comparable<Node>{
        int row;
        int col;
        int wall;

        Node(int row, int col, int wall) {
            this.row = row;
            this.col = col;
            this.wall = wall;
        }

        @Override
        public int compareTo(Node o) {
            return this.wall - o.wall;
        }
    }

    static void bfs(int row, int col) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(row, col, 0));
        visited[row][col] = true;

        Node node;
        int crow, ccol, mrow, mcol;
        while (!pq.isEmpty()) {
            node = pq.poll();
            crow = node.row;
            ccol = node.col;

            if (crow == N - 1 && ccol == M - 1) {
                System.out.println(node.wall);
                return;
            }

            for (int dir = 0; dir < 4; dir++) {
                mrow = crow + delR[dir];
                mcol = ccol + delC[dir];

                if (mrow < 0 || mcol < 0 || N <= mrow || M <= mcol || visited[mrow][mcol]) continue;

                visited[mrow][mcol] = true;

                if (map[mrow][mcol] == 1) pq.offer(new Node(mrow, mcol, node.wall + 1));
                else pq.offer(new Node(mrow, mcol, node.wall));
            }
        }
    }

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

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

        map = new int[N][M];
        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }

        visited = new boolean[N][M];

        bfs(0, 0);

        br.close();
    }
}

 

알고리즘 문제) BOJ 1389. 케빈 베이컨의 6단계 법칙

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

문제 요약

• BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성
  • 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산
  • 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합

시간 제한

• 2초

입력

• 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)
• M개의 줄에는 친구 관계
  • 친구 관계는 중복되어 들어올 수도 있으며,
  • 친구가 한 명도 없는 사람은 없다.
  • 모든 사람은 친구 관계로 연결되어져 있다

출력

• 케빈 베이컨의 수가 가장 작은 사람을 출력
• 여러 명일 경우에는 번호가 가장 작은 사람을 출력

코드

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

public class Main {
    static int N, M;
    static ArrayList<Integer>[] list;
    static Queue<Integer> q = new LinkedList<>();
    static boolean[] visited;

    static int bfs(int node, int target) {
        q.offer(node);
        visited[node] = true;

        int cur, size, cnt = 0;
        while (!q.isEmpty()) {
            size = q.size();

            for (int i = 0; i < size; i++) {
                cur = q.poll();

                if (cur == target){
                    q.clear();
                    return cnt;
                }

                for (Integer nxt : list[cur]) {
                    if (visited[nxt]) continue;

                    q.offer(nxt);
                    visited[nxt] = true;
                }
            }

            cnt++;
        }
        return -1;
    }

    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());

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

        int node1, node2;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            node1 = Integer.parseInt(st.nextToken());
            node2 = Integer.parseInt(st.nextToken());

            list[node1].add(node2);
            list[node2].add(node1);
        }

        visited = new boolean[N + 1];
        int sum, ansNode = 0, ansSum = 1 << 30, tmp;
        for (int i = 1; i <= N; i++) {
            sum = 0;

            for (int j = 1; j <= N; j++) {
                if (i == j) continue;

                tmp = bfs(i, j);

                sum += tmp;

                Arrays.fill(visited, false);
            }

            if (ansSum > sum) {
                ansSum = sum;
                ansNode = i;
            }
        }

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