[Baekjoon] 9944_NxM 보드 완주하기

Gold III

문제(출처: https://www.acmicpc.net/problem/9944)

---

< NxM 보드 완주하기 >

 

문제 풀이

 

이동하려는 곳을 미리 확인한 후 보드 범위 밖이거나 이미 방문한 곳이라면 방향을 바꾸도록 구현했다.

 

종료 조건을 어떻게 설정해야 하는가 고민했다. 처음에는 visited 배열을 이용해서 반복문을 활용해서 확인하려다가 시간이 오래 걸릴 것 같아 따로 변수를 두어 개수로 다 방문했는지 확인했다. 

 

 

 

 my solution (Java)

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

public class _9944_ { // NxM 보드 완주하기
	static int arr[][], n, m, min_result;
	static boolean visited[][];
	static int dx[] = { -1, 1, 0, 0 }; // 상하좌우
	static int dy[] = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;

		int num = 1;
		String input="";
		while ((input = bf.readLine())!= null) {
			st=new StringTokenizer(input);
			n = Integer.parseInt(st.nextToken()); // 세로 크기
			m = Integer.parseInt(st.nextToken()); // 가로 크기
			
			arr = new int[n][m];
			visited = new boolean[n][m];
			min_result = -1;
			int result = 1;
			int cnt = 1; // 방문 개수

			for (int i = 0; i < n; i++) {
				String str = bf.readLine();
				for (int j = 0; j < m; j++) {
					char c = str.charAt(j);
					arr[i][j] = c;
					if (c == '*') {
						cnt += 1;
						visited[i][j] = true;
					}
				}
			}

			if(cnt== n*m) min_result=0; // 한 칸만 빈 칸이라면
			
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (!visited[i][j]) {
						for (int k = 0; k < 4; k++) {
							if(i+dx[k]>=0 && i+dx[k]<n && j+dy[k]>=0 && j+dy[k]<m && !visited[i+dx[k]][j+dy[k]]) { // 이동 가능 & 방문 x
								visited[i][j] = true;
								search(i, j, result, k, cnt);
								visited[i][j] = false;
							}	
						}
					}
				}
			}
			System.out.println("Case " + num + ": " + min_result);
			num += 1;
		}
	}

	private static void search(int i, int j, int result, int direct, int cnt) {

		if (cnt == n * m) { // 모든 빈 칸 방문
			if (min_result == -1 || min_result > result) {
				min_result = result;
				return;
			}
		}

		int x = i + dx[direct];
		int y = j + dy[direct];
		
		if (x >= 0 && x < n && y >= 0 && y < m && !visited[x][y]) { // 보드 범위 안 & 방문 x
			visited[x][y] = true;
			search(x, y, result, direct, cnt + 1);
			visited[x][y] = false;
		} else { // 방향 변경
			for (int k = 0; k < 4; k++) { 
				if (k == direct) 
					continue;
				int a = i + dx[k];
				int b = j + dy[k];
				if (a >= 0 && a < n && b >= 0 && b < m && !visited[a][b]) { // 보드 범위 안 & 방문 x
					visited[a][b] = true;
					search(a, b, result + 1, k, cnt + 1);
					visited[a][b] = false;
				}
			}
		}
	}
}

 

Main

- 세로 크기(n), 가로 크기(m) 입력

- arr : 보드 상태 저장

  visited : 방문 여부 저장

  min_result : 최소 이동 횟수

  result : 이동 횟수

  cnt : 방문 개수

- 보드 상태 입력받으며 장애물이 있는 곳은 cnt +1 및 방문 표시

- 한 칸만 빈칸이라면 min_result=0

  ex) 3 3

        ***
        *.*

        ***

-  arr를 탐색하며 빈칸이며 이동할 곳이 보드 범위 안이고 아직 방문하지 않은 곳이면 방문 표시 및 search 함수 호출

- min_result 출력

 

search(x좌표, y 좌표, 이동 횟수, 방향 번호, 방문 개수)

- 종료 조건 : 모든 빈칸을 방문했다면 min_result 값을 최소 이동 횟수로 업데이트한 후 종료

- 방향에 맞게 이동한 후 보드 범위 안이며 아직 방문하지 않았다면 -> 그 방향으로 계속 이동 가능하다는 뜻이므로 방문 표시 및 search 함수 호출 (cnt만 1 증가)

- 보드 범위 안이 아니거나 이미 방문한 곳이라면 방향을 바꿔야 함 -> 방향을 바꿔서 이동할 위치가 보드 범위 안이고 아직 방문하지 않았다면 방문 표시 및 search 함수 호출 (방향을 바꿨으므로 result를 1 증가 및 cnt 1 증가)

 

---

마무리🤔

 

NullPointer 에러가 발생해서 설마 하고 입력을 받는 부분을 찾아보니 EOF에서 에러가 발생하는 것이었다.

---