[BOJ] #13023 ABCDE, 프로그래머스 블록이동하기

#13023 ABCDE

문제설명

5명의 인물이 모두 연결 되어 있으면 1출력
5명의 인물이 모두 연결 되어 있지 않으면 0을 출력해준다.

 

 

해결방법

친구관계의 연결을 '이중행렬'로 표현했고 관계파악은 dfs와 백트래킹으로 해주었다. 여기서 다시 유의할 점은
1. 시작 노드가 정해지지 않았으니까 모든 경로에서 dfs를 돌려야한다.

2. A부터 D까지 경로는 5니까 cnt가 5일때까지만 찾으면 된다.

3. 백트레킹으로 경로가 실패한 경우에는 되돌아가줘야 한다.

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BojABCDE {
    static int n, m;
    static int arr[][];
    static boolean visited[];
    static boolean found = false; // 성공 여부 확인을 위한 플래그 변수

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(input.readLine());
        n = Integer.parseInt(tokens.nextToken());
        m = Integer.parseInt(tokens.nextToken());
        arr = new int[n][n];
        visited = new boolean[n];

        for (int i = 0; i < m; i++) {
            tokens = new StringTokenizer(input.readLine());
            int a = Integer.parseInt(tokens.nextToken());
            int b = Integer.parseInt(tokens.nextToken());
            arr[a][b] = 1;
            arr[b][a] = 1;
        }

        // 모든 노드에서 DFS를 시작해봄
        for (int i = 0; i < n; i++) {
            dfs(i, 1);  // 각 노드에서 시작할 때 깊이를 1로 시작
            if (found) break;  // 이미 성공한 경우 더 이상 탐색하지 않음
        }

        // 성공 여부에 따라 출력
        if (found) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    static void dfs(int x, int depth) {
        if (depth == 5) {  // 깊이가 5에 도달하면 성공
            found = true;
            return;
        }

        visited[x] = true;  // 현재 노드를 방문처리
        for (int i = 0; i < n; i++) {
            if (arr[x][i] == 1 && !visited[i]) {  // 연결된 노드가 방문되지 않았다면
                dfs(i, depth + 1);  // 깊이를 증가시키며 DFS
                if (found) return;  // 성공한 경우 더 이상 탐색하지 않음
            }
        }
        visited[x] = false;  // 백트래킹: 다시 방문 가능하도록 설정
    }
}

 

---

프로그래머스 블록이동하기

개인적으로 어려운 문제였다.. 그림이 복잡함을 유도해서 그렁가..

3차원 배열을 쓸 생각은 전혀 못했었는데 이 문제를 풀며 필요하다면 3차원 배열도 적극 써봐야 겠다는 생각

문제설명

이 문제는 2칸의 블록을 상하좌우로 이동하거나 회전시켜서 (N-1, N-1) 좌표에 도달하는 최단 시간을 구하는 문제이다. 블록은 두 칸을 차지하며, 가로로 눕거나 세로로 설 수 있다. 블록은 상하좌우로 움직일 수 있고, 벽이 없는 공간에서는 회전할 수 있다.

이동 방법:

1. 상하좌우 이동: 블록은 상하좌우로 이동할 수 있으며, 두 칸 모두 빈 공간이어야 한다.
2. 회전: 블록이 가로로 누워있다면 세로로 회전할 수 있고, 세로로 서있다면 가로로 회전할 수 있다. 회전은 블록의 양쪽 끝 중 하나를 축으로 돌며, 회전할 때도 회전할 공간이 모두 비어있어야 회전이 가능하다.

 

해결방법

이 문제는 BFS를 사용하여 해결할 수 있다. 블록의 상태(두 칸의 좌표와 방향)를 저장하고, 상하좌우 이동 및 회전을 통해 가능한 경로를 모두 탐색하며 최단 시간을 구할 수 있다.

 

1. 상태 표현

블록은 두 개의 칸을 차지하므로 두 개의 좌표로 상태를 표현해야 한다. 따라서 (x1, y1), (x2, y2)로 블록의 상태를 나타낸다.

블록이 가로로 누워있으면 방향은 0, 세로로 서있으면 방향은 1로 구분한다.

 

2. BFS 탐색

BFS는 큐를 이용하여 블록의 현재 상태와 이동 횟수를 저장한다.

블록이 상하좌우로 이동할 수 있는지 확인한 후, 이동할 수 있으면 그 상태를 큐에 추가한다.

회전도 가능하면 큐에 추가한다.

BFS의 특성상 먼저 도착한 경로가 최단 경로이므로, 목적지에 도달하면 바로 종료하고 시간을 반환한다.

 

3. 방문 처리

블록의 현재 상태(두 좌표와 방향)를 visited 배열에 기록하여 중복된 경로를 탐색하지 않도록 한다.

방문 기록은 블록의 좌표와 방향(가로/세로)에 따라 3차원 배열로 저장한다.

 

4. 상하좌우 이동

블록이 가로로 있을 때와 세로로 있을 때 각각 상하좌우로 이동하는 경우를 모두 따져본다.

이동하려는 좌표가 보드의 범위를 벗어나지 않고, 벽이 없으며, 두 좌표 모두 유효한지 확인한다.

 

5. 회전 처리

블록이 가로로 있을 때 세로로 회전할 수 있는 경우와, 세로로 있을 때 가로로 회전할 수 있는 경우를 모두 따진다.

회전할 때는 블록의 양 끝점에서 회전하며, 회전할 공간이 모두 비어 있어야 회전이 가능하다.

 

전체코드

import java.util.*;

class Solution {
    static boolean[][][] visited;
    static int[][] deltas = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 상하좌우 이동
    static int N;

    public int solution(int[][] board) {
        N = board.length;
        visited = new boolean[N][N][2]; // 3차원 배열로 가로/세로 상태를 기록

        return bfs(board);
    }

    public int bfs(int[][] board) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {0, 0, 0, 1, 0}); // 시작 좌표 (x1, y1), (x2, y2), 이동 횟수
        visited[0][0][0] = true;

        while (!queue.isEmpty()) {
            int[] robot = queue.poll();
            int x1 = robot[0], y1 = robot[1], x2 = robot[2], y2 = robot[3], count = robot[4];

            // 목적지에 도달하면 최단 경로 반환
            if ((x1 == N - 1 && y1 == N - 1) || (x2 == N - 1 && y2 == N - 1)) {
                return count;
            }

            // 상하좌우 이동
            for (int[] delta : deltas) {
                int nx1 = x1 + delta[0], ny1 = y1 + delta[1];
                int nx2 = x2 + delta[0], ny2 = y2 + delta[1];

                if (isValid(nx1, ny1, nx2, ny2, board, x1, y1)) {
                    queue.offer(new int[] {nx1, ny1, nx2, ny2, count + 1});
                    visited[nx1][ny1][0] = true; // 가로 상태로 이동
                    visited[nx2][ny2][0] = true; // 가로 상태로 이동
                }
            }

            // 회전 처리
            rotate(queue, x1, y1, x2, y2, board, count);
        }

        return -1; // 목적지에 도달할 수 없을 때
    }

    // 유효성 체크 함수
    public boolean isValid(int x1, int y1, int x2, int y2, int[][] board, int dir) {
        if (x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0 || x1 >= N || y1 >= N || x2 >= N || y2 >= N) {
            return false;
        }
        if (board[x1][y1] == 1 || board[x2][y2] == 1 || visited[x1][y1][dir] || visited[x2][y2][dir]) {
            return false;
        }
        return true;
    }

    // 회전 처리 함수
    public void rotate(Queue<int[]> queue, int x1, int y1, int x2, int y2, int[][] board, int count) {
        if (x1 == x2) { // 가로 상태
            // 위쪽으로 회전
            if (x1 - 1 >= 0 && board[x1 - 1][y1] == 0 && board[x2 - 1][y2] == 0) {
                if (!visited[x1 - 1][y1][1]) {
                    queue.offer(new int[] {x1, y1, x1 - 1, y1, count + 1});
                    visited[x1 - 1][y1][1] = true;
                }
                if (!visited[x2 - 1][y2][1]) {
                    queue.offer(new int[] {x2, y2, x2 - 1, y2, count + 1});
                    visited[x2 - 1][y2][1] = true;
                }
            }
            // 아래쪽으로 회전
            if (x1 + 1 < N && board[x1 + 1][y1] == 0 && board[x2 + 1][y2] == 0) {
                if (!visited[x1 + 1][y1][1]) {
                    queue.offer(new int[] {x1, y1, x1 + 1, y1, count + 1});
                    visited[x1 + 1][y1][1] = true;
                }
                if (!visited[x2 + 1][y2][1]) {
                    queue.offer(new int[] {x2, y2, x2 + 1, y2, count + 1});
                    visited[x2 + 1][y2][1] = true;
                }
            }
        }
        // 세로 상태도 동일하게 처리 가능
    }
}