윤주

윤주

꾸준히 기록하자

BOJ 1175 배달

메모리 : 13896 KB

시간 : 104 ms

BOJ 1175 배달 Gold 1


풀이

문제의 핵심 부분은

  1. 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하게 2개 있다.
  2. 같은 방향으로 두 번 연속으로 이동할 수 없다.
  3. 만약 불가능 할 때는 -1을 출력한다.

라고 생각했다.
두 곳을 다 배달한 걸 어떻게 알려줘야 할까? 고민하다가 이전에 비트마스크로 풀었던 문제가 생각나서 그것을 응용해보았다.
2번같은 경우는 bfs를 진행하면서 큐에 저장된 값과 비교하며 같은 방향은 가지 않도록 했다.
그런데 3번에서 어떻게 처리해야할지 감이 안잡히고 방문 배열이 필요없을 것 같아서 (갔던 곳을 또 갈 수 있으니까) 방문 배열 없이 진행했더니 시간 초과가 났다…
결국 다른 사람들 문제 풀이 참고해서 4차원 배열을 사용했단 걸 알게 되고..!
무사히 통과할 수 있었다.


느낀점

4차원 배열이라니… 상태를 기록한다는 것이 무엇인지 더 고민해봐야겠다.
처음엔 비트마스크로 풀다가 저장할 상태가 2개뿐이라 1과 2로 더하기만 했다.
비트마스크로 풀 때 좀 안 익숙해서.. 헤맸는데 비트마스크 연습도 잊지 말자!
그리고 종료 조건에 만족하는 값을 어디서 비교해주는 게 좋을지도 고민해봐야겠다
어떨 땐 큐에서 꺼내고 바로 검사할 때도 있었고, 큐에 넣을 때 검사할 때도 있었다.
큰 차이는 없어 보이지만 코드를 짜면서 조금 헤매는 기분이었다..


코드

import java.io.*;
import java.util.*;

public class BOJ1175 {
	static int N, M, ans;
	static char[][] map;
	static int[] start;
	static int[][] dest;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static boolean[][][][] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		start = new int[2];
		dest = new int[2][2];
		visited = new boolean[N][M][4][4]; // N, M, 방향, 배달장소
		int index = 0;
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
				if (map[i][j] == 'S') {
					start[0] = i;
					start[1] = j;
				} else if (map[i][j] == 'C') {
					dest[index][0] = i;
					dest[index][1] = j;
					index++;
				}
			}
		}
		
		ans = -1;
		bfs();
		System.out.println(ans);
	}
	
	public static void bfs() {
		Queue<Pos> q = new LinkedList<>();
		q.offer(new Pos(start[0], start[1], -1, 0));
		for (int i = 0; i < 4; i++) {
			visited[start[0]][start[1]][i][0] = true;
		}
		int time = 0;
		while (!q.isEmpty()) {
			int size = q.size();
			for (int s = 0; s < size; s++) {
				Pos cur = q.poll();
				int status = cur.status;
				if (cur.x == dest[0][0] && cur.y == dest[0][1]) {
					if (status != 1) status += 1; 
				} else if (cur.x == dest[1][0] && cur.y == dest[1][1]) {
					if (status != 2) status += 2;
				}
				if (status == 3) {
					ans = time;
					return;
				}
				for (int d = 0; d < 4; d++) {
					if (cur.d == d) continue;
					int nx = cur.x + dir[d][0];
					int ny = cur.y + dir[d][1];
					if (!isRange(nx, ny)) continue;
					if (map[nx][ny] == '#') continue;
					if (visited[nx][ny][d][status]) continue;
					q.offer(new Pos(nx, ny, d, status));
					visited[nx][ny][d][status] = true;
				}
			}
			time++;
		}
	}
	
	private static boolean isRange(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < M) return true;
		else return false;
	}

	static class Pos {
		int x, y;
		int d;
		int status;
		public Pos(int x, int y, int d, int status) {
			super();
			this.x = x;
			this.y = y;
			this.d = d;
			this.status = status;
		}
	}
}

참고