<백준> 24.07.01에 푼 문제들

1. 미로 탐색 (Silver 1)

[백준]

https://www.acmicpc.net/problem/2178

[깃허브]

ForCodeKata/baekjoon 문제집/2178 미로 탐색 at main · heesoo-park/ForCodeKata

제출 결과

---

현재 위치를 가는데까지 걸린 횟수를 저장하는 2차원 배열을 만들어 쉽게 해결했다.

 

작성한 코드는 다음과 같다.

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

public class Main {
    
    static char[][] maze = new char[101][101];
    static int[][] history = new int[101][101];
    static boolean[][] visited = new boolean[101][101];
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static int n, m;
    
    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());
        
        for (int i = 1; i <= n; i++) {
            String line = br.readLine();
            for (int j = 1; j <= m; j++) {
                maze[i][j] = line.charAt(j - 1);
            }
        }
        
        bfs();
        
        bw.write(String.valueOf(history[n][m]));
        bw.flush();
        bw.close();
    }
    
    static void bfs() {
        
        Queue<Position> q = new LinkedList<>();
        history[1][1] = 1;
        visited[1][1] = true;
        q.offer(new Position(1, 1));
        
        while (!q.isEmpty()) {
            Position cur = q.poll();
            
            for (int i = 0; i < 4; i++) {
                int newR = cur.r + dy[i];
                int newC = cur.c + dx[i];
                
                if (newR > n || newR < 1 || newC > m || newC < 1) continue;
                if (maze[newR][newC] == '0' || visited[newR][newC]) continue;
                
                history[newR][newC] = history[cur.r][cur.c] + 1;
                visited[newR][newC] = true;
                q.offer(new Position(newR, newC));
            }
        }
    }
    
    static class Position {
        int r, c;
        
        Position(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

 

2. 숨바꼭질 (Silver 1)

[백준]

https://www.acmicpc.net/problem/1697

[깃허브]

ForCodeKata/baekjoon 문제집/1697 숨바꼭질 at main · heesoo-park/ForCodeKata

제출 결과

---

1차원 배열로 생각하고 BFS 특징으로 특정 위치에 다른 방식으로 도착하기 전에 도착한다면 가장 빠른 방법이라는 것을 사용하여 해결했다.

 

작성한 코드는 다음과 같다.

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

public class Main {
    
    static int[] road = new int[100001];
    static boolean[] visited = new boolean[100001];
    static int n, k;
    
    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 = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        bfs();
        
        bw.write(String.valueOf(road[k]));
        bw.flush();
        bw.close();
    }
    
    static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        visited[n] = true;
        q.offer(n);
        
        while (!q.isEmpty()) {
            int cur = q.poll();
            
            if (cur == k) break;
            
            int prevStep = cur - 1;
            if (prevStep >= 0 && !visited[prevStep]) {
                visited[prevStep] = true;
                road[prevStep] = road[cur] + 1;
                q.offer(prevStep);
            } 
            
            int nextStep = cur + 1;
            if (nextStep <= 100000 && !visited[nextStep]) {
                visited[nextStep] = true;
                road[nextStep] = road[cur] + 1;
                q.offer(nextStep);
            } 
            
            int doubleStep = 2 * cur;
            if (doubleStep <= 100000 && !visited[doubleStep]) {
                visited[doubleStep] = true;
                road[doubleStep] = road[cur] + 1;
                q.offer(doubleStep);
            }
        }
    }
}

 

3. 나이트의 이동 (Silver 1)

[백준]

https://www.acmicpc.net/problem/7562

[깃허브]

ForCodeKata/baekjoon 문제집/7562 나이트의 이동 at main · heesoo-park/ForCodeKata

제출 결과

---

이번 문제를 풀면서 배열 내의 값을 초기화하는 메서드인 Arrays.fill 사용법을 알게 되었다.

또한 Kotlin에서 주로 봤던 형태의 반복문도 사용해봤다.

 

작성한 코드는 다음과 같다.

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

public class Main {
    
    static int[][] board = new int[301][301];
    static boolean[][] visited = new boolean[301][301];
    static int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
    static int[] dx = {2, 1, -1, -2, -2, -1, 1, 2};
    
    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;
        
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {           
            int l = Integer.parseInt(br.readLine());
            
            st = new StringTokenizer(br.readLine());
            int startR = Integer.parseInt(st.nextToken());
            int startC = Integer.parseInt(st.nextToken());
            
            st = new StringTokenizer(br.readLine());
            int targetR = Integer.parseInt(st.nextToken());
            int targetC = Integer.parseInt(st.nextToken());
            
            bfs(l, new Position(startR, startC), new Position(targetR, targetC));
            bw.write(String.valueOf(board[targetR][targetC]) + "\n");
            
            cleanBoard();
        }
        
        bw.flush();
        bw.close();
    }
    
    static void bfs(int len, Position start, Position target) {
        Queue<Position> q = new LinkedList<>();
        visited[start.r][start.c] = true;
        q.offer(start);
        
        while (!q.isEmpty()) {
            Position cur = q.poll();
            
            if (cur.r == target.r && cur.c == target.c) break;
            
            for (int i = 0; i < 8; i++) {
                int newR = cur.r + dy[i];
                int newC = cur.c + dx[i];
                
                if (newR >= len || newR < 0 || newC >= len || newC < 0) continue;
                if (visited[newR][newC]) continue;
                
                visited[newR][newC] = true;
                board[newR][newC] = board[cur.r][cur.c] + 1;
                q.offer(new Position(newR, newC));
            }
        }
    }
    
    static void cleanBoard() {
        for (int[] line : board) {
            Arrays.fill(line, 0);
        }
        
        for (boolean[] line : visited) {
            Arrays.fill(line, false);
        }
    }
    
    static class Position {
        int r, c;
        
        Position(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}