소프티어

파이썬 DFS 구현했는데 시간 초과 원인을 잘 모르겠어요

DFS 가지치기 잘하면 괜찮다고 하길래 중복 제거하려고 시점,방향,위치 고려한 가지치기 진행했는데도 여전히 시간 초과가 발생하네요. 오래 생각해봤는데도 이유를 잘 모르겠습니다. 혹시 짐작 가는 부분이 있으신 분이 계신가요? import sys def dfs(depth, si, sj, sd, visited): # visited 관리 [i,j,d,t]: t시간에 (i,j)위치를 향해 d방향으로 들어옴   global global_visited   if depth == T:     global_visited.extend(visited)     return   rotary_key = arr[si][sj][depth%4]   rotary_val = rotaryType[rotary_key]   if rotary_val[0] == sd:     flag = 0     for d in rotary_val[1]:       ni, nj = si+di[d], sj+...

JS

T가 100이 최대라서 재귀 DFS 되겠지 하고 썼는데, 런타임 에러 나니깐 쓰면 안됩니다. 아마도. const fs = require('fs'); const input = fs.readFileSync('input.txt', 'utf8').trim().split(/\n+/); const [N, T] = input[0].split(/\s+/).map(Number); const crossSignals = input.slice(1).map(line => line.split(/\s+/).map(Number)); const top = 0b1000 const bottom = 0b0100 const left = 0b0010 const right = 0b0001 const SIGNAL_LIST = [     // 1     {         from: left,         to: top | right | bottom,     },     // 2 ...

C++ 반례 부탁드립니다.

#include <algorithm> #include <cstdio> #include <cmath> #include <iostream> #include <queue> #include <utility> #include <vector> using namespace std; #define PER_INTERSECTION_SIGNALS 4 #define SIG_TYPES 12 #define MAX_SIGS  4 typedef pair<int, int> position; const position NO_SIG = { 0, 0 }; const position LEFT = { -1, 0 }; const position UP = { 0, -1 }; const position RIGHT = { 1, 0 }; const position DOWN = { 0, 1 }; const position SIG_DIRS[MAX_SIGS] = {     RIGH...

dfs 풀이 오류좀 찾아봐 주실 수 있을까요

n,T = map(int,input().split()) signals = [list(map(int,input().split())) for _ in range(n**2)] # print(signals) L = [0,-1] R = [0,1] U = [-1,0] D = [1,0] ## 1번 리스트 [R U R D] 에서 제일 앞의 R은 해당 신호에 통과하기 위한 올바른 방향입니다. R U L D 가 순서대로 순환하며 들어 가 있습니다 signal_dict = [[],[R,U,R,D],[U,L,U,R],[L,U,L,D],[D,L,D,R], [R,U,R],[U,L,U],[L,L,D],[D,D,R], [R,R,D],[U,U,R],[L,L,U],[D,L,D]] # dir = signal_dict[1] # print(dir[0]) # print(dir[1]) answer = [[0,0]] import sys n,T = map(int,sys.stdin.readline().split()) sig...

테스트 케이스 b8한개만 오답이라고 나옵니다.. 반례 부탁드립니다!

특수한 케이스가 문제인가 싶기도 한데 도저히 감을 못잡겠어서 질문드립니다! gpt 보고 메모리 누수 관련해서 수정해봤는데 결과는 똑같습니다.. #include <stdio.h> #include <stdlib.h> typedef struct sig_info {   int into;   int len;   int to[3]; }Info; typedef struct car{   int x, y, into, t;   struct car* tail; }Car; typedef struct Queue{   struct car* front;   struct car* rear; } Queue; int** sig; int Q_len = 0; Info I[13]; Car car; Car* head; int** vst; Queue* Q; void Q_init() {   head = (Car*)malloc(sizeof...

반례좀 찾아주실 수 있을까요?

import sys from collections import deque signals = { # 들어오는 방향, 갈수 있는 방향  "1": ["r", ["u", "r", "d"]],   "2": ["u", ["l", "u", "r"]],  "3": ["l", ["u", "l", "d"]],  "4": ["d", ["l", "d", "r"]],  "5": ["r", ["u", "r"]],  "6": ["u", ["l", "u"]],  "7": ["l", ["l", "d"]],  "8": ["d", ["d", "r"]],  "9": ["r", ["r", "d"]],  "10": ["u", ["u", "r"]],  "11": ["l", ["l", "u"]],  "12": ["d", ["l", "d"]], } move = {"u": (0, -1), "l": (-1, 0), "r...

차세대 지능형 교통시스템 반례좀 찾아주세요 ㅜㅜ

vs code로 넣고 디버깅하면서 돌려봐도 맞는거같은데 히든테케중에 틀리는게 꽤 많네요ㅜㅜ import sys from collections import deque input = sys.stdin.readline def bfs(row,colum,time,dir): # (행,열,시간,진입방향) global N,T dq=deque() dq.append((row,colum,time,dir)) cnt=0 while dq: r,c,t,d = dq.popleft() if not visit[r][c]: cnt+=1 visit[r][c]=1 if t>=T: continue light = roads[r*N+c][t%4]-1 if dir!=light%4: continue ...

차세대 지능형 교통시스템 질문입니다.

4 4도 넣어봤는데 제가 계산 했을 때의 답이 나온 것을 확인 했습니다.. 어떤 조건에서 답이 틀리게 나오는지 궁금합니다. 예제 ) #define _CRT_SECURE_NO_WARNINGS #include //차의 방향에 따라 //(1), (5), (9) : Right 방향 - 나머지 1 //(2), (6), (10) : Up 방향 - 나머지 2 //(3), (7), (11) : Left 방향 - 나머지 3 //(4), (8), (12) : Down 방향 - 나머지 0 int N, CrossRoad[101][101][4] = { 0, }, check[101][101] = { 0, }, queue[10001][4] = { 0, }, count = 0; int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; //하우상좌 int signal[12][4] = { {1,1,1,0}, {0,1,1,1}, {1,0,1,1}, {1,1,0,...

차세대 지능형 교통시스템

출력 형식은 '이동 경로에 있는 모든 교차로 갯수' 출력이라고 나와있는데, 해설은 '마지막으로 방문했던 교차로' 찾는 걸로 해설이 나와있네요. 어떤 것이 맞는건가요? -------------------------------------------------------------------------------------------------------------------------------

차세대 지능형 교통시스템 반례좀 부탁드립니다.

import sys # input N, T = map(int, input().split()) signals = [[]*N for _ in range(N)] for x in range(N): for y in range(N): signals[y].append(list(map(int, input().split()))) l = 'left' r = 'right' u = 'up' d = 'down' signal_def = [ [r,[u,r,d]],[u,[l,u,r]],[l,[u,l,d]],[d,[l,d,r]], [r,[r,u]],[u,[u,l]],[l,[l,d]],[d,[d,r]], [r,[r,d]],[u,[u,r]],[l,[l,u]],[d,[d,l]], ] signal_map = {l:(-1,0), r:(1,0), u:(0,-1), d:(0,1)} dir_map = {l:0, r:1, u:2, d:3} ...