[2823] 유턴 싫어

🔗 문제 링크

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

🔍 문제 설명

상근이는 여자친구와의 드라이브를 위해서 운전을 배우고 있다. 도로 연수를 10년쯤 하다 보니 운전은 그럭저럭 잘하게 되었다. 하지만, 그는 유턴을 하지 못한다. 10년동안 도로 연수를 받았지만 유턴을 하지 못한다. 밥먹고 유턴만 연습했지만, 결국 유턴은 하지 못했다.

상근이는 유턴을 연습하기 위해서 시간을 투자하는 대신에 유턴을 할 필요가 없고, 유턴이 금지된 마을로 이사가려고 한다.

상근이가 이사가려고 하는 마을은 막다른 길이 있으면 안 된다. 막다른 길은 유턴을 하지 않고는 빠져나올 수 없기 때문이다. 어떤 마을의 지도가 주어졌을 때, 유턴을 하지 않고 마을의 모든 구역을 돌아다닐 수 있는지 없는지(막다른 길이 있는지 없는지)를 구하는 프로그램을 작성하시오.

마을의 지도는 R × C 칸으로 이루어진 표로 생각할 수 있다. 각 칸에 빌딩이 있다면 'X'로 표시하고, 길이라면 '.'으로 표시한다. 모든 칸은 빌딩 또는 길이다. 상근이가 어떤 길 위에 있다면, 근처 네 방향(위,아래,오른쪽,왼쪽)의 길로 이동할 수 있다. 빌딩으로는 이동할 수 없다.

이 마을에 막다른 길이 없다면, 상근이는 임의의 한 길에서 시작해서, 갈 수 있는 어떤 방향으로 움직이더라도, 유턴을 하지 않고 그 위치로 돌아올 수 있어야 한다.

유턴은 방금 이동한 방향의 반대 방향으로 이동하는 것을 말한다.

⚠️ 제한사항

• 3 ≤ R, C ≤ 10

• 모든 길은 서로 연결되어 있다

• 마을에는 적어도 두 개의 길이 있다

---

🗝 풀이 (언어 : Java)

처음에 BFS, DFS 방식으로 원점에 다시 돌아올 수 있는지 체크하는 방식으로 작성했는데, 오답 처리되었다.
반례를 못찾겠어서 다른 사람들의 아이디어를 이용해서 작성했다. 길인 모든 점을 체크해서 해당 점이 갈 수 없는 방향이 3개의 이상이면 유턴이 불가능하다고 판단한다.

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

public class Main {

	private static final int[] dx = {-1, 1, 0, 0};
	private static final int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int row = Integer.parseInt(st.nextToken());
		int col = Integer.parseInt(st.nextToken());
		String[][] matrix = new String[row][col];
		for (int i = 0; i < row; i++) {
			String[] split = br.readLine().split("");
			System.arraycopy(split, 0, matrix[i], 0, col);
		}
		br.close();
		solution(matrix);
	}

	private static void solution(String[][] matrix) {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				int count = 0;
				if (matrix[i][j].equals(".")) {
					for (int k = 0; k < 4; k++) {
						int x = i + dx[k];
						int y = j + dy[k];
						if (x < 0 || x >= matrix.length
						|| y < 0 || y >= matrix[0].length
						|| matrix[x][y].equals("X")) {
							count++;
						}
					}
					if (count >= 3) {
						System.out.println(1);
						return;
					}
				}
			}
		}
		System.out.println(0);
	}
}