[SWEA]1953.탈주범 검거

bfs로 푸는 문제였다. 그런데 파이프가 연결되어 있는 지점으로만 이동이 가능하기 때문에 현재지점에서 상하좌우를 확인하여 연결이 된 지점으로만 탐색을 수행해야한다. 

 

현재 지점의 파이프 번호에 따라서 탐색할 수 있는 방향이 정해져 있다. 예를 들면 현재 지점의 파이프번호가 2번이면 어차피 좌우로는 이동할 수 없기 때문에 상하 방향만 탐색하도록 한다. 이처럼 파이프 번호에 따라 탐색할 방향을 for문 안에서 미리 걸러주었다. 

 

문제를 풀 때 한가지 착각을 했다. y좌표가 + 되는 것이 아래로 이동하는 방향이고 - 되는 것이 위로 이동하는 방향인데 이것을 반대로 생각해서 계속 틀렸다. 방향에 주의하자.

 

private static void bfs() {

		visited[R][C] = true;
		q.add(new Point(C, R));

		int time = 0;
		while (true) {
			time++;
			if (time == L) {				
				break;
			}

			int size = q.size();
			for (int j = 0; j < size; j++) {
				Point p = q.poll();
				int curX = p.x;
				int curY = p.y;
				int curPipe = map[curY][curX];

				for (int i = 0; i < 4; i++) { // 0:하 1:상 2:우 3:좌
					if (curPipe == 2 && (i == 2 || i == 3))         // 각 파이프마다 막혀있는 방향은 탐색 X
						continue;
					else if (curPipe == 3 && (i == 0 || i == 1))
						continue;
					else if (curPipe == 4 && (i == 0 || i == 3))
						continue;
					else if (curPipe == 5 && (i == 1 || i == 3))
						continue;
					else if (curPipe == 6 && (i == 1 || i == 2))
						continue;
					else if (curPipe == 7 && (i == 0 || i == 2))
						continue;

					int nextX = curX + dx[i];
					int nextY = curY + dy[i];

					if (nextX >= 0 && nextY >= 0 && nextX < M && nextY < N) {
						int nextPipe = map[nextY][nextX];

						if (nextPipe != 0 && !visited[nextY][nextX]) {

							// 각 방향마다 터널이 연결되어 있으면 방문하고 q에 삽입 
							if (i == 0) { // 하 
								if (nextPipe == 1 || nextPipe == 2 || nextPipe == 4 || nextPipe == 7) {
									visited[nextY][nextX] = true;
									q.add(new Point(nextX, nextY));
								}
							} else if (i == 1) { // 상 
								if (nextPipe == 1 || nextPipe == 2 || nextPipe == 5 || nextPipe == 6) {
									visited[nextY][nextX] = true;
									q.add(new Point(nextX, nextY));
								}
							} else if (i == 2) { // 우 
								if (nextPipe == 1 || nextPipe == 3 || nextPipe == 6 || nextPipe == 7) {
									visited[nextY][nextX] = true;
									q.add(new Point(nextX, nextY));
								}
							} else if (i == 3) { // 좌 
								if (nextPipe == 1 || nextPipe == 3 || nextPipe == 4 || nextPipe == 5) {
									visited[nextY][nextX] = true;
									q.add(new Point(nextX, nextY));
								}
							}
						}
					}
				}
			}
		}
	}

 

<전체코드>