SOFT_안전운전을 도와줄 차세대 지능형 교통시스템_6274 (Java)

문제링크

느낀점

• 너무 계속 틀려서 진짜,,,화가났다,,
• 오답과 시간초과만 나오면 모르겠는데, 정답도 상당 수 있어서 분명 특정 경우를 고려 안한건데 뭔지를 몰랐다.
• 다른 풀이를 참고해서야 알았는데, 그것도 내가 코드 읽어보고 눈치챈게 아니라 ai가 코드 차이 분석에서 알려줬다,, 이런식이면 큰일인디
• 그래도 문제가 너무 쉽다 싶었는데, 간과했던 부분을 깨달을 수 있어서 다행이다,,

설계 : 15분

• 각 교차로와 시간에 따른 신호 배열, 신호에 따른 진입방향과 전진 가능 방향에 대한 배열을 잘 정리한다.
• 처음 방문하는 교차로만 카운트 하며 dfs 한다.
• 이때 방문하는 교차로의 현재 신호의 진입방향과 교차로로 오던 방향이 일치해야 다음으로 넘어갈 수 있다.
• 신호는 4T마다 반복되기 때문에 신호가 반복되는 주기 안에 싸이클이 발생하면 중단한다.
  • entered배열을 사용해서 특정 교차로에 특정 주기에 특정 방향으로 진입한 적이 있는지 판단한다.

코드(Java)

• 구현 시간: 120분

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

public class Main {

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int[][] direc = {{}, {0, 1, 2},{3, 0, 1},{2, 3, 0},{3, 2, 1},{0, 1},{3, 0},{3, 2},{2, 1},{1, 2},{0, 1},{0, 3},{3, 2}};
    static int[] entrance = {0, 1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2};

    static int n;
    static int t;
    static int answer;
    static boolean[][] visited;
    static int[][][] signal;
    static boolean[][][][] entered;
    
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        t = Integer.parseInt(input[1]);

        signal = new int[n][n][4];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int s = 0; s < 4; s++) {
                    signal[i][j][s] = Integer.parseInt(st.nextToken());
                }
            }
        }

        visited = new boolean[n][n];
        entered = new boolean[n][n][4][4];
        answer = 0;
        dfs(0, 0, 0, 0);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int time, int r, int c, int from) {
        if (time > t) return;
    
        if (!visited[r][c]) {
            visited[r][c] = true;
            answer++;
        }

        int nt = time % 4;
        if (entered[r][c][nt][from]) return;
        entered[r][c][nt][from] = true;
        
        int currentSignal = signal[r][c][nt];
        if (entrance[currentSignal] != from) return;
        for (int d : direc[currentSignal]) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                dfs(time + 1, nr, nc, d);
            }
        }
    }
}