[백준/Java] 2823번 : 유턴 싫어

🌵 문제 분석

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

RxC 크기의 마을이 주어질 때 (X는 빌딩, .은 길)

임의의 한 길에서 유턴하지 않고 그 위치로 돌아올 수 있는지 출력하라.

돌아올 수 있다면 0, 돌아올 수 없다면 1 출력

 

입력:

R C

RxC크기의 마을 지도

🌵 구현 아이디어

모든 길에 대해 상하좌우로 2개 이상의 길이 연결되어있는지 확인한다.

 

예제1)

5 5
XX.XX
X...X
.....
X...X
XX.XX

(2, 0), (4, 2), (2, 0), (2, 4)좌표는 인접한 곳에 1개의 길만 연결되어있으므로 다시 돌아올 수 없다. (막다른길) -> 1을 출력함

 

예제2)

3 9
...XXX...
.X.....X.
...XXX...

이 경우는 모든 길의 인접한 곳에 2개 이상의 길이 연결되어있으므로 막다른 길이 없다. -> 0을 출력함

🌵 시간 복잡도

탐색하는 길 좌표의 최대 개수 : O(R*C)

길의 상하좌우 탐색 : O(1)

 

전체 시간복잡도 : O(R*C)

R, C<=10 이므로 1초 안에 연산 가능하다.

🌵 알고리즘

그래프 탐색

🌵 코드 설계

1. 입력 받기
   1. int변수에 R, C 저장
   2. arr[R][C] 배열에 길, 벽 저장
2. 하나의 길에 대해 상하좌우 탐색하는 함수 isIsolated() 
   1. x, y 좌표를 받아 상하좌우를 탐색하여 .개수를 센다.
   2. 벽이거나 범위를 벗어나면 패스
   3. .이 1개면 true를, 1개 초과면 false를 반환
3. 하나라도 false이면 1을 출력하고 그렇지 않으면 0을 출력

🌵 정답 코드

import java.util.*;

public class Main {
    static int R, C;
    static char[][] arr;
    static int[] dx = {-1, 1, 0, 0}; // 상하좌우 이동
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        arr = new char[R][C];
        
        for (int i = 0; i < R; i++) {
            String line = sc.next();
            for (int j = 0; j < C; j++) {
                arr[i][j] = line.charAt(j);
            }
        }
        
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (arr[i][j] == '.' && isIsolated(i, j)) {
                    System.out.println(1);
                    return;
                }
            }
        }
        System.out.println(0);
    }
    
    static boolean isIsolated(int x, int y) {
        int count = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < R && ny < C && arr[nx][ny] == '.') {
                count++;
            }
        }
        return count == 1;
    }
}