[BOJ] 문제 풀이 모음집 - BFS/DFS 2 (JAVA)

13549: 숨바꼭질 3

🔗 문제 링크

• BFS 탐색으로 최소 시간을 구하면 됨
• 순간이동은 0초, X+1 또는 X-1로 이동하는 것은 1초가 걸리므로 순간이동을 먼저 수행하는 것이 좋음

24.07.01 풀이

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

public class Main {
    static final int MAX = 100_000;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        System.out.println(bfs(N, K));
    }

    static int bfs(int n, int k) {
        int[] time = new int[MAX + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        time[n] = 1;

        while (!queue.isEmpty()) {
            int now = queue.poll();
            if (now == k) break;

            // 순간이동은 0초가 걸리므로 가장 먼저 수행하기
            int next = now * 2;
            if (next <= MAX && time[next] == 0) {
                time[next] = time[now];
                queue.offer(next);
            }

            // X-1로 이동하는 것은 1초가 걸림
            next = now - 1;
            if (next >= 0 && time[next] == 0) {
                time[next] = time[now] + 1;
                queue.offer(next);
            }

            // X+1로 이동하는 것은 1초가 걸림
            next = now + 1;
            if (next <= MAX && time[next] == 0) {
                time[next] = time[now] + 1;
                queue.offer(next);
            }
        }
        return time[k] - 1;
    }
}

 

1600: 말이 되고픈 원숭이

🔗 문제 링크

• 총 K번 말처럼 뛸 수 있음 ⇒ 말처럼 뛴 횟수에 따라 방문할 수 있는 지점이 달라짐
  • 즉, 말처럼 뛴 횟수에 따라 상태가 달라짐 ⇒ 방문 처리 시, 3차원 배열 사용하기
• 따라서 visited = new boolean[H][W][K + 1]로 선언해야 함
  • visited[x][y][0]: 말처럼 0번 뛴 경우
  • visited[x][y][1]: 말처럼 1번 뛴 경우
  • ...

전에 풀었던 문제라 그런지 외워서 푸는 느낌이 강하다. 새로운 BFS/DFS 문제들을 많이 접해볼 필요를 느꼈다.. 

24.07.02 풀이

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

public class Main {
    static int K, W, H;
    static int[][] board;
    static boolean[][][] visited;
    static int[][] jump = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
    static int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        board = new int[H][W];
        visited = new boolean[H][W][K + 1];

        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < W; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(bfs());
    }

    static int bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, 0, 0, 0));
        visited[0][0][0] = true;

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            int x = now.x, y = now.y;
            if (x == H - 1 && y == W - 1) {
                return now.dist;
            }

            // 우선 원숭이처럼 이동하기
            for (int i = 0; i < 4; i++) {
                int nx = x + move[i][0];
                int ny = y + move[i][1];
                if (nx < 0 || ny < 0 || nx >= H || ny >= W || visited[nx][ny][now.jump]) {
                    continue;
                }

                if (board[nx][ny] == 0) { // 평지면 이동 가능
                    queue.offer(new Node(nx, ny, now.jump, now.dist + 1));
                    visited[nx][ny][now.jump] = true;
                }
            }

            // 말처럼 이동할 수 있는 횟수가 남은 경우
            if (now.jump < K) {
                for (int i = 0; i < 8; i++) {
                    int nx = x + jump[i][0];
                    int ny = y + jump[i][1];
                    if (nx < 0 || ny < 0 || nx >= H || ny >= W || visited[nx][ny][now.jump + 1]) {
                        continue;
                    }

                    if (board[nx][ny] == 0) { // 평지면 이동 가능
                        queue.offer(new Node(nx, ny, now.jump + 1, now.dist + 1));
                        visited[nx][ny][now.jump + 1] = true;
                    }
                }
            }
        }
        return -1;
    }

    static class Node {
        int x, y;
        int jump; // 말처럼 움직인 횟수
        int dist; // 이동 횟수

        public Node(int x, int y, int jump, int dist) {
            this.x = x;
            this.y = y;
            this.jump = jump;
            this.dist = dist;
        }
    }
}

 

13913: 숨바꼭질 4 

🔗 문제 링크

• 전에 풀었던 숨바꼭질 문제와 동일하게 풀면 됨
• 이때, 이동 경로를 기록해야 하므로 배열을 하나 더 추가해서 풀면 됨

점은 0 ~ 100,000 사이에 위치할 수 있는데, if (now == 0) break; 와 같은 식으로 점의 위치가 0인 것을 고려하지 않아서 틀렸다. 다시 풀어보자..!

24.07.03 풀이

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

public class Main {
    static int N, K;
    static final int MAX = 100_000;
    static int[] time, record;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        time = new int[MAX + 1];
        record = new int[MAX + 1];
        record[N] = -1;

        StringBuilder sb = new StringBuilder();
        int dist = bfs();
        int now = K;
        sb.append(now);
        while (true) {
            now = record[now];
            if (now == -1) break;
            sb.insert(0, now + " ");
        }
        sb.insert(0, dist + "\n");
        System.out.println(sb.toString());
    }

    static int bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(N);
        time[N] = 1;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            if (now == K) break;

            int next = now - 1;
            if (next >= 0 && time[next] == 0) {
                queue.offer(next);
                time[next] = time[now] + 1;
                record[next] = now;
            }

            next = now + 1;
            if (next <= MAX && time[next] == 0) {
                queue.offer(next);
                time[next] = time[now] + 1;
                record[next] = now;
            }

            next = now * 2;
            if (next <= MAX && time[next] == 0) {
                queue.offer(next);
                time[next] = time[now] + 1;
                record[next] = now;
            }
        }
        return time[K] - 1;
    }
}

 

14442: 벽 부수고 이동하기 2

🔗 문제 링크

• 벽 부수기 문제와 풀이 방식이 동일함
• 다른 점은 벽을 여러 개 부술 수 있다는 것 ⇒ 부순 벽의 수에 따라 방문할 수 있는 곳이 달라짐
  • visited 배열을 3차원으로 생성하기: visited[N][M][K + 1]

24.07.04 풀이

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

public class Main {
    static int N, M, K;
    static int[][] map;
    static boolean[][][] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M][K + 1];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        System.out.println(bfs());
    }

    static int bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, 0, 0, 0));
        visited[0][0][0] = true;

        int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            int x = now.x, y = now.y;
            if (x == N - 1 && y == M - 1) {
                return now.dist + 1;
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + move[i][0];
                int ny = y + move[i][1];
                if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
                    continue;
                }

                if (map[nx][ny] == 1) { // 이동하려는 지점이 벽인 경우
                    if (now.crash < K && !visited[nx][ny][now.crash + 1]) {
                        queue.offer(new Node(nx, ny, now.crash + 1, now.dist + 1));
                        visited[nx][ny][now.crash + 1] = true;
                    }
                } else if (map[nx][ny] == 0 && !visited[nx][ny][now.crash]) {
                    queue.offer(new Node(nx, ny, now.crash, now.dist + 1));
                    visited[nx][ny][now.crash] = true;
                }
            }
        }
        return -1;
    }

    static class Node {
        int x, y;
        int crash; // 벽을 부순 횟수
        int dist; // 이동 횟수

        public Node(int x, int y, int crash, int dist) {
            this.x = x;
            this.y = y;
            this.crash = crash;
            this.dist = dist;
        }
    }
}

 

16933: 벽 부수고 이동하기 3 

🔗 문제 링크

• 벽 부수기 문제와 풀이 방식이 동일함
  • 다른 점은 낮에만 벽을 부술 수 있다는 것 & 해당 자리에 그대로 있을 수 있다는 것
• 벽이 있음 & 낮 & 벽을 부술 수 있는 기회가 남은 경우 ⇒ 벽을 부수고 이동하기
• 기존의 자리에 그대로 있을 수 있다 == 기존 자리에 남아있을 때 장점이 있다는 것
  • 장점은 막힌 벽을 부술 수 있다는 것 (더 짧은 새로운 길이 생길 수 있으므로)
  • 따라서 밤일 때만 기존 자리에 남아있도록 하면 시간 초과가 발생하지 않음

기존 자리에 있을 수 있다는 것을 그냥 그대로 해석해서 코드를 작성했었다. 그러니 시간 초과를 맞이했다... 기존 자리에 남아있을 때의 장점이 있으므로 남아있지 않을까?라는 생각이 들었고 그러려면 밤일 때 기존의 자리에서 기다려야 다음날 벽을 부술 수 있다는 것을 깨닫게 되었다..! 처음 보는 조건이 있으면 그냥 넘어가지 말고, "왜 이 조건이 추가됐지? 의도가 뭘까?"라는 생각까지 하도록! 

24.07.05 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

import javax.security.auth.x500.X500Principal;
import javax.tools.Diagnostic;

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

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visited = new boolean[N][M][K + 1];
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = line.charAt(j) - '0';
			}
		}
		System.out.println(bfs());
	}

	static int bfs() {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(0, 0, 0, 1, true));
		visited[0][0][0] = true;

		int[][] move = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
		while (!queue.isEmpty()) {
			Node now = queue.poll();
			int x = now.x, y = now.y;
			if (x == N - 1 && y == M - 1) {
				return now.dist;
			}

			// 현재 자리에 머무르는 것이 더 짧은 경로이려면 다음날 벽을 부수려고 그러는 것? 그렇담 밤에만 자기 자리에 있도록?
			if (!now.day) {
				queue.offer(new Node(x, y, now.crash, now.dist + 1, !now.day));
				visited[x][y][now.crash] = true;
			}
			
			for (int i = 0; i < 4; i++) {
				int nx = x + move[i][0];
				int ny = y + move[i][1];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M)
					continue;

				// 벽이 있는 곳 & 낮인 경우 & 벽을 부술 기회가 남은 경우
				if (map[nx][ny] == 1 && now.day && now.crash < K) {
					if (!visited[nx][ny][now.crash + 1]) {
						queue.offer(new Node(nx, ny, now.crash + 1, now.dist + 1, !now.day));
						visited[nx][ny][now.crash + 1] = true;
					}
				} else if (map[nx][ny] == 0 && !visited[nx][ny][now.crash]) {
					queue.offer(new Node(nx, ny, now.crash, now.dist + 1, !now.day));
					visited[nx][ny][now.crash] = true;
				}
			}
		}

		return -1;
	}

	static class Node {
		int x, y;
		int crash; // 부순 벽의 개수
		int dist; // 이동한 칸의 개수
		boolean day; // 낮/밤 여부

		public Node(int x, int y, int crash, int dist, boolean day) {
			this.x = x;
			this.y = y;
			this.crash = crash;
			this.dist = dist;
			this.day = day;
		}
	}
}

 

16920: 확장 게임

🔗 문제 링크

• Si 만큼 이동할 수 있는 모든 칸에 성을 만듦
  • 2만큼 움직인다고 할 때, → 방향으로 1번, ↓ 방향으로 1번 이런 식으로 진행 가능함
  • 각 플레이어마다 큐를 가지도록 해서 구현하기

주말 내내 붙들고 있었다..🤧 예전에는 풀었던데 이번에는 왜 이렇게 헤맸을까 실력이 퇴화됐나 보다.. 다시 꼭 풀어서 실력을 다시 키워보자! 

24.07.07 풀이

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

public class Main {
    static int N, M, P;
    static char[][] map;
    static boolean[][] visited;
    static Player[] players;
    static int[][] record, after;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        visited = new boolean[N][M];
        players = new Player[P + 1];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= P; i++) {
            int move = Integer.parseInt(st.nextToken());
            players[i] = new Player(move);
        }
        record = new int[N][M];

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
                if (map[i][j] != '.' && map[i][j] != '#') {
                    int player = map[i][j] - '0';
                    players[player].queue.offer(new int[]{i, j});
                    players[player].castle++;
                    visited[i][j] = true;
                    record[i][j] = player;
                }
            }
        }

        bfs();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= P; i++) {
            sb.append(players[i].castle).append(" ");
        }
        System.out.println(sb);
    }

    static void bfs() {
        int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean isChange = true;
        while (isChange) {
            isChange = false;
            for (int p = 1; p <= P; p++) { // 각 플레이어 순서대로 성 확장하기
                Queue<int[]> queue = players[p].queue;
                int moveCnt = 0; // 이동 횟수
                while (!queue.isEmpty()) {
                    moveCnt++;
                    int size = queue.size();
                    for (int s = 0; s < size; s++) {
                        int[] now = queue.poll();

                        for (int i = 0; i < 4; i++) {
                            int nx = now[0] + move[i][0];
                            int ny = now[1] + move[i][1];
                            if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny] || map[nx][ny] == '#') {
                                continue;
                            }

                            queue.offer(new int[]{nx, ny});
                            visited[nx][ny] = true;
                            record[nx][ny] = p;
                            players[p].castle++;
                            isChange = true;
                        }
                    }
                    // 이동을 완료하면 확장 종료하기
                    if (moveCnt == players[p].move) break;
                }
            }
        }
    }

    static class Player {
        int move; // 이동 가능 횟수
        int castle; // 가진 성의 개수
        Queue<int[]> queue = new LinkedList<>();

        public Player(int move) {
            this.move = move;
            this.castle = 0;
        }
    }
}