2회차 코딩 테스트 오답 풀이

 1번 문제는 BFS (너비 우선 탐색, Breadth First Search)알고리즘을 사용해 출발 지점부터 목표 지점까지의 최단 경로를 찾는 문제였다. 

 

BFS?

• bfs는 그래프 탐색 알고리즘 중 하나로, 시작점에서 인접점들을 먼저 탐색한 후, 그 다음 인접점들을 탐색하는 방식이다.
• BFS는 최단 경로를 찾는 데 유리하다.
• BFS는 큐를 사용해 구현되며, 각 정점을 방문할 때마다 그 정점의 인접한 정점들을 큐에 추가한다.
• 이 문제에서는 BFS를 사용해 시작 위치에서 목표 위치까지의 최단 경로를 찾고 그 거리를 반환한다. 

import java.util.*;

public class Solution {

    public int solution(int[][] maps) {
        //n,m은 각각 maps 배열의 행과 열의 길이를 나타낸다.
        int n = maps.length;
        int m = maps[0].length;


        // 방향 벡터 정의 (상, 하, 좌, 우)
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        // BFS를 위한 큐와 방문 배열 초기화
        Queue<int[]> queue = new LinkedList<>(); //BFS를 수행하기 위한 큐
        boolean[][] visited = new boolean[n][m]; //각 위치의 방문 여부 기록

        // 시작 위치 초기화
        queue.add(new int[]{0, 0});
        visited[0][0] = true;

        // BFS 수행
        int distance = 1; //현재가지의 이동 거리를 나타낸다. 
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int x = current[0];
                int y = current[1];

                // 목표 위치에 도달한 경우
                if (x == n - 1 && y == m - 1) {
                    return distance;
                }

                // 4가지 방향으로 이동
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];

                    // 이동 가능한 위치인지 확인
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && maps[nx][ny] == 1) {
                        queue.add(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }
            distance++;
        }

        // 목표 위치에 도달하지 못한 경우
        return -1;
    }
}

• 0은 벽, 1은 이동 가능 공간을 나타낸다. 
• n과 m 변수를 사용해 미로의 행과 열의 길이를 저장한다.
• 상하좌우 이동을 위한 방향 벡터 dx, dy를 배열에 저장한다.
• BFS를 위해 큐와 방문 여부를 나타내는 2차원 visted배열을 초기화한다.
• 큐에는 시작 위치 (0,0) 를 추가하고 해당 위치를 방문했다고 표시한다.
• BFS를 수행한다. 큐가 비어 있지 않은 동안 다음 과정을 반복한다.
  • 큐에서 하나의 위치를 꺼낸다
  • 해당 위치에서 상하좌우 이동이 가능한지 확인한다.
  • 이동 가능하다면 큐에 추가, 방문 여부를 표시한다.
  • 도착 지점에 도달하면 현재까지의 거리를 반환한다.
• 만약 도착 지점에 도달하지 못하면 -1을 반환한다.

 

2번 문제

 그리드에 연결된 구성 요소의 수를 찾는 알고리즘을 구현한 것이다. DFS(깊이 우선 탐색). BFS(너비 우선 탐색)을 사용해 구현할 수 있다.

import java.util.*;

public class Solution {

    public int solution(int n, int m, int[][] points) {
        //grid는 n+1 * m+1 크기의 2차원 배열. 각 위치에 점이 있는지여부를 나타낸다.
        // true는 점이 있는 위치, false는 점이 없는 위치를 나타낸다.
        boolean[][] grid = new boolean[n + 1][m + 1];

        // points에 해당하는 위치를 true로 설정
        for (int[] point : points) {
            int x = point[0];
            int y = point[1];
            grid[x][y] = true;
        }

        // BFS를 위한 방향 설정 (상, 하, 좌, 우)
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // BFS 함수
        Queue<int[]> queue = new LinkedList<>(); 

        int componentCount = 0;

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (!grid[i][j]) {
                    componentCount++;
                    queue.add(new int[]{i, j});
                    grid[i][j] = true;

                    while (!queue.isEmpty()) {
                        int[] current = queue.poll();
                        int x = current[0];
                        int y = current[1];

                        for (int[] direction : directions) {
                            int nx = x + direction[0];
                            int ny = y + direction[1];

                            if (nx >= 0 && nx <= n && ny >= 0 && ny <= m && !grid[nx][ny]) {
                                queue.add(new int[]{nx, ny});
                                grid[nx][ny] = true;
                            }
                        }
                    }
                }
            }
        }

        return componentCount;
    }

• 그리드의 크기 n,m. 그리드 상의 포인트 위치를 나타내는 points 배열을 입력 받는다.
• grid 배열을 생성해 각 위치를 방문했는지 여부를 나타낸다. 처음에는 모두  false로 초기화 된다.
• points배열에 있는 위치를 grid에 표시한다. 이 위치들은 연결된 구성 요소의 시작점이 된다.
• 상하좌우로 이동하기 위한 방향을 정의한다.
• 각 위치를 순회하면서 해당 위치가 방문되지 않았다면 새로운 연결된 구성 요소를 발견한 것으로 간주하고 bfs를 시작한다. bfs를 통해 해당 구성 요소에 속하는 모든 위치를 방문한다.
• fs가 종료되면 새로운 구성 요소의 카운트를 증가시킨다.
• 모든 위치를 순회한 후, 발견된 구성 요소의 수를 반환한다.

 

3번 문제

 2차원 배열에서 각 숫자의 이동 거리를 계산하는 문제를 해결하는 알고리즘을 구현한 것이다. 

이 알고리즘은 각 숫자별로 이동 거리를 계산해 배열에 저장한 후, 해당 배열을 반환한다.

import java.util.Arrays;

public class Solution {
    public static int[] solution(int[][] arr) {
        int rows = arr.length;
        int cols = arr[0].length;
        int[] distances = new int[cols];

        // 각 숫자별로 이동 거리 계산
        for (int num = 0; num < cols; num++) {
            int totalDistance = 0;
            int currentCol = -1;

            // 첫 행에서 출발점 찾기
            for (int c = 0; c < cols; c++) {
                if (arr[0][c] == num) {
                    currentCol = c;
                    break;
                }
            }

            // 다음 행으로 이동하면서 거리 계산
            for (int r = 1; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (arr[r][c] == num) {
                        totalDistance += Math.abs(currentCol - c);
                        currentCol = c;
                        break;
                    }
                }
            }

            distances[num] = totalDistance;
        }

        return distances;
    }
}

• solution 메서드는 2차원 배열 arr를 입력 받는다. 이 배열은 숫자로 이루어진 행렬을 나타낸다.
• rows 와 cols변수를 사용해 행과 열의 수를 저장한다. 또한 각 숫자의 이동 거리를 저장할 배열 distance를 생성한다.
• 각 숫자별로 이동 거리를 계산하기 위해 다음을 반복한다
  • 현재 숫자의 이동 거리를 저장할 변수 totalDistance를 초기화한다.
  • 출발점인 첫 번째 행에서 해당 숫자가 있는 열을 찾는다.
  • 다음 행부터 시작하여 해당 숫자가 있는 열을 찾으면서 이동 거리를 계산한다.
  • 이동 거리는 이전 열에서 현재 열까지의 절대값으로 계산된다.
  • 각 행마다 현재 열을 업데이트한다
• 각 숫자의 이동 거리를 계산한 후, 해당 값을 distance 배열에 저장한다.
• distance 배열을 반환한다.

이 알고리즘은 입력 배열을 한 번만 순회하므로 시간 복잡도는 O(rows * cols) 이다.