백준 : 1400

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

1400번: 화물차

 

처음에는 시간이 필요할것 같은 문제여서 3차원 visitd르 접근하였다. 꾸역꾸역 문제를 풀엇지만 다른사람을 보고 생각지도 못햇던 방향으로 풀어서 적어보려고한다.

 

1. 3차원 배열을 만들 필요가없다. 

이유 : 화물차가 기다리는 곳은 신호가 잇는곳 뿐이다. 따라서 신호앞에서 건너가지 못할겨우만 그 Queue는 그대로 다음 시간대에 보존시켜주면된다.

 

이렇게하면 최단 시가리 유지가 되는가?? 

 

이것도 visit 배열은 Queue의 매번 한사이클마다 돌게되면 시간의 증가함에따라 이동을 할 수있다.

 

그때 어던 교차로에서 기다렷다가 가는 상황에서 교차로가 이미 방문 햇다면 지금은 죽은 노드이기때문에 처내는게

가능하다.

 

package 삼성;

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

public class 화물차 {
	// 01:20 ~

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

	static int N, M;

	static char[][] map;
	static boolean visit[][];

	static int cnt;

	static class Pair {
		int y;
		int x;

		public Pair(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}
	}

	// 최대 800초
	static int sy, sx;
	static int ey, ex;

	static class Signal {
		int dir;
		int a;
		int b;

		public Signal(int dir, int a, int b) {
			super();
			this.dir = dir;
			this.a = a;
			this.b = b;
		}
	}

	static Signal sig[];

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

		while (true) {
			st = new StringTokenizer(br.readLine());
			cnt = 0;
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			if (N == 0 && M == 0)
				break;

			map = new char[N][M];
			visit = new boolean[N][M];

			for (int i = 0; i < N; i++)
				map[i] = br.readLine().toCharArray();

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (map[i][j] >= '0' && map[i][j] <= '9') {
						cnt++;
					}

					if (map[i][j] == 'A') {
						sy = i;
						sx = j;
					}

					if (map[i][j] == 'B') {
						ey = i;
						ex = j;
					}
				}
			}

			// cnt 만큼 조사한다
			sig = new Signal[cnt];

			for (int i = 0; i < cnt; i++) {
				st = new StringTokenizer(br.readLine());
				int n = Integer.parseInt(st.nextToken());
				int d = st.nextToken().equals("-") ? 0 : 1;
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				// d : 0 동서 , d : 1 남북
				sig[n] = new Signal(d, a, b);
			}
			br.readLine();

			// 답을 구한다.
			int ans = BFS();
			if (ans == -1) {
				sb.append("impossible\n");
			} else {
				sb.append(ans).append('\n');
			}
		}
		System.out.println(sb.toString());
	}

	public static int BFS() {
		int time = 0;
		Queue<Pair> q = new LinkedList<Pair>();
		q.add(new Pair(sy, sx));
		visit[sy][sx] = true;

		while (!q.isEmpty()) {
			int size = q.size();
			for (int s = 0; s < size; s++) {
				Pair cur = q.poll();

				if (cur.y == ey && cur.x == ex) {
					return time;
				}

				// 이동한다.
				for (int d = 0; d < 4; d++) {
					int ny = cur.y + dy[d];
					int nx = cur.x + dx[d];
					if (ny < 0 || nx < 0 || ny >= N || nx >= M)
						continue;
					if (visit[ny][nx])
						continue;
					if (map[ny][nx] == '.')
						continue;
					if (map[ny][nx] == '#' || map[ny][nx] == 'A' || map[ny][nx] == 'B') {
						visit[ny][nx] = true;
						q.add(new Pair(ny, nx));
					}

					if (map[ny][nx] >= '0' && map[ny][nx] <= '9' && d != 4) {
						int snum = map[ny][nx] - '0';
						if (checkSignal(snum, d, time)) {
							visit[ny][nx] = true;
							q.add(new Pair(ny, nx));
						}else {
							q.add(new Pair(cur.y,cur.x));
						}
					}
				}
			}
			time++;
		}

		return -1;
	}

	public static boolean checkSignal(int snum, int d, int time) {

		// dir ==0 동서 dir == 1 남북
		int dir = sig[snum].dir;
		int a = sig[snum].a;
		int b = sig[snum].b;
		int ans = 0;
		time = time % (a + b);

		// 동서가 먼저일때
		if (dir == 0) {
			if (time - a >= 0) {
				ans = (dir + 1) % 2;
			} else {
				ans = dir;
			}

		} else {
			if (time - b >= 0) {
				ans = (dir + 1) % 2;
			} else {
				ans = dir;
			}
		}

		// ans =0 동서 ans =1 남북
		// d 0
		if (ans == 0 && (d == 0 || d == 1))
			return true;
		if (ans == 1 && (d == 2 || d == 3))
			return true;

		return false;
	}

}