문제

https://softeer.ai/practice/6274

---

입력

입력으로는 N과 시간 T가 첫 줄에 주어진다.

다음 N2개의 줄에 각 교차로의 신호 집합이 주어진다.

신호는 항상 4개이며, 순서는 X축부터 진행을 한다.

---

출력

이동 경로에 있는 모든 교차로의 개수를 출력한다. 한번 갔던 교차로는 중복해서 세지 않는다.

---

풀이

제한조건

• 1 ≤ N, T ≤ 100

접근방법

문제가 매우 복잡해보이지만, 단순 탐색이다.
차량의 진행방향과 신호의 방향만 추가적으로 고려해주자.

단순 BFS로 탐색하면 된다.
차량의 진행방향과 신호의 방향을 잘 고려해야한다.

또한 일반적으로 BFS를 이용한 탐색을 할 경우, 방문한 지점에 대해서 더 이상 방문하지 않는다.

하지만 이 문제의 경우, 차량이 해당 교차로에 도착한 시점, 차량의 진입 방향에 따라 동일한 교차로에 진입하였으나, 다시 새로운 경로로 갈 수 있는 경우가 있다.

각자의 방식으로 아래를 정의해보자.

1. 차량의 진행 방향을 어떻게 기록할 것인가?
2. 12개의 신호를 어떻게 정의할 것인가?
3. 시간과 관련된 부분을 어떻게 처리할 것인가?
4. 이미 방문한 지점은 어떻게 확인할 것인가?

1. Car Class 를 생성하여, 현재 좌표와 차량의 진행방향을 기록해 둠.

2. 12개의 신호를 모두 정의함.
   new TrafficLight(3,"1101")

   0 : 상, 1 : 하, 2 : 좌, 3 : 우
   따라서 위 신호는 차량이 오른쪽으로 향할때 보는 신호이고(3),
   "1101"은 index에 따라 진행 가능한 신호를 나타낸다.
   즉 0,1,3번째가 1이므로 상, 하, 우로 이동 가능

	static class TrafficLight{
		int dir; // 특정 방향에서 보는 신호.
		String type; // 해당 방향으로 갈 수 있는지.
		TrafficLight(int a, String s){
			dir = a;
			type = s;
		}
	
	static TrafficLight[] trafficLight = {
		new TrafficLight(-1,""),
		new TrafficLight(3,"1101"), // 1
		new TrafficLight(0,"1011"),
		new TrafficLight(2,"1110"),
		new TrafficLight(1,"0111"),
		new TrafficLight(3,"1001"),
		new TrafficLight(0,"1010"),
		new TrafficLight(2,"0110"),
		new TrafficLight(1,"0101"),
		new TrafficLight(3,"0101"),
		new TrafficLight(0,"1001"),
		new TrafficLight(2,"1010"),
		new TrafficLight(1,"0110") // 12
	};

3. 이중 While문을 통해, BFS에서 Depth(시간)을 처리하였음.

4. 시간, 방향과 상관없이 해당 교차로에 처음 가는 순간만 카운팅하는 방식
   이미 방문했더라도 여러번 Queue에 계속 넣으며 탐색. 그러나 재방문시 카운팅을 하지 않음.
   -> 재방문 시 Queue에 넣지 않기 위해서는 x,y좌표, 방문 방향, 방문 시간을 모두 고려해야 함.

---

코드

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

public class Main {
	static int N, T;
	static List<Integer>[][] map;

	static class Car{
		int x; 
		int y;
		int dir; // 차량의 진행 방향

		Car(int a, int b, int c){
			x = a;
			y = b;
			dir = c;
		}
	}

	static class TrafficLight{
		int dir; // 특정 방향에서 보는 신호.
		String type; // 해당 방향으로 갈 수 있는지.
		TrafficLight(int a, String s){
			dir = a;
			type = s;
		}
	}
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
    // 신호 타입 12개
	static TrafficLight[] trafficLight = {
		new TrafficLight(-1,""),
		new TrafficLight(3,"1101"), // 1
		new TrafficLight(0,"1011"),
		new TrafficLight(2,"1110"),
		new TrafficLight(1,"0111"),
		new TrafficLight(3,"1001"),
		new TrafficLight(0,"1010"),
		new TrafficLight(2,"0110"),
		new TrafficLight(1,"0101"),
		new TrafficLight(3,"0101"),
		new TrafficLight(0,"1001"),
		new TrafficLight(2,"1010"),
		new TrafficLight(1,"0110") // 12
	};

	public static void main(String[] args) throws Exception{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] inputs = in.readLine().split(" ");
		N = stoi(inputs[0]);
		T = stoi(inputs[1]);

		map = new List[N][N];
		for(int i = 0 ; i< N; ++i){
			for(int j = 0 ; j< N; ++j){
				map[i][j] = new ArrayList();
				inputs = in.readLine().split(" ");
				for(int k = 0 ; k < 4; ++k)
					map[i][j].add(stoi(inputs[k]));
			}
		}

		int result = search(new Car(0,0,0), T);

		System.out.println(result);
	}

	public static int search(Car start, int limit){
		int result = 1; // 최초에 1개 지점에 도달.

		Queue<Car> q = new ArrayDeque();
		q.add(start);

		int time = 0 ;
		boolean[][] visit = new boolean[N][N];
		visit[start.x][start.y] = true;
		while(!q.isEmpty()){
			int size = q.size();
			while(size-- > 0){
				Car c = q.poll();

				int lightType = map[c.x][c.y].get(time % 4);

				// 차량의 방향이 신호의 방향과 다르다. 정지.
				if(c.dir != trafficLight[lightType].dir){
					continue;
				}

				for(int d = 0; d < 4; ++d){
					// 특정 방향으로 가는 신호가 있는 경우 갈 수 있다.
					if(trafficLight[lightType].type.charAt(d) == '1'){
						int nextX = c.x + dx[d];
						int nextY = c.y + dy[d];
						if(isInRange(nextX, nextY)){
                        	// 해당 교차로에 처음 온다면, 카운팅
							if(!visit[nextX][nextY]){
								result++;
								visit[nextX][nextY] = true;
							}
							q.add(new Car(nextX, nextY, d));
						}
					}
				}

			}
			time++;
			if(time >= limit)
				break;
		}

		return result;
	}

	public static boolean isInRange(int x, int y){
		if(0 <= x && x < N && 0 <=y && y < N)
			return true;
		return false;
	}
	public static int stoi(String s){
		return Integer.parseInt(s);
	}
}