소프티어

시간 초과 관련해서 질문 있습니다.

유령의 위치를 큐에 한번에 넣어 bfs를 수행하는 경우 시간초과가 발생합니다. 하지만 탈출구랑 가장 가까이 있는 유령의 위치를 구하고 해당 위치에서 bfs를 돌고 풀이를 하면 정답처리를 받습니다. 두 경우 모두 시간 복잡도가 O(N^2) 아닌가요? 왜 첫번째 케이스에서 시간초과가 발생하는지 궁금합니다. (두 코드 영역을 제외한 나머지 코드는 동일합니다 1) 모든 유령 위치에서 한번에 bfs int[][] ghostTime = new int[N][M]; // 유령이 [i,j] 에 도착하는 시간 Arrays.stream(ghostTime).forEach(g -> Arrays.fill(g, Integer.MAX_VALUE)); Queue<int[]> q = new LinkedList<>(); for (int[] x : ghost) { q.add(x); ghostTime[x[0]][x[1]] = 0; } // 유령이 각 {i,j}를 가장 빨리 도착하는 시...

#4, #12 오답

import sys N,M = map(int,input().split()) arr = [list(map(str,input().split())) for _ in range(N)] # 0 빈칸, 1 벽, 2 출구, 3 남우, 4 유령 new_arr = [[0] * M for _ in range(N)] ghost = [] for i in range(N): for j in range(M): if arr[i][0][j] == 'D': ei,ej = i,j new_arr[i][j] = 2 elif arr[i][0][j] == 'N': si,sj = i,j new_arr[i][j] = 3 elif arr[i][0][j] == 'G': ghost.append((i,j)) new_arr[i][j] = 4 elif arr[i][0][j] == '#': new_arr[i][j] = 1 else: new_arr[i][j] = 0 arr = new_arr from collections import d...

반례 추가 필요

1 5 D#..N 이와 같이, 유령이 존재하지 않으며 그냥 출구에 도달할 수 없는 경우에 대한 반례가 추가 필요합니다. 남우와 유령이 누가 먼저 출구에 도달할 수 있는지로 코드를 짰을 때, 해당 내용에 대한 예외 처리가 되어 있지 않은 코드가 정답을 받습니다.

파이썬 시간초과문제

import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) grid = [list(sys.stdin.readline().strip()) for _ in range(n)] ds = [(1, 0), (-1, 0), (0, 1), (0, -1)] ghost_pos_list = [] for i in range(n):     for j in range(m):         if grid[i][j] == 'D':             dest_pos = [i, j]         elif grid[i][j] == 'G':             ghost_pos_list.append([i, j])         elif grid[i][j] == 'N':             start_pos = [i, j] def calc_na...

12번 케이스만 통과 못합니다... 제가 어떤 반례를 못찾은걸까요?

#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cmath> #include <climits> using namespace std; const int dx[4] = {-1, 1, 0 ,0}; const int dy[4] = {0, 0, -1, 1}; int bfs(vector<vector<char>>& map, vector<vector<bool>>& visited, pair<int, int> coord, bool can_pass_wall) { int rows = map.size(); int cols = map[0].size(); queue<pair<pair<int, int>, int>> q; // {{x, y}, move_cnt} q.push({coord, 0}); visited[coord.first...

파이썬 시간 초과가 뜨는데 시간 단축 할 방법이 있을까요

import sys from collections import deque import copy #### module import #### q = deque() ghost = deque() exit = [] #Exit index initial_dist = 0 n, m = map(int, sys.stdin.readline().split()) array = [] for i in range(n): li = list(input()) if 'N' in li: x, y = i, li.index('N') a = [] a.append((x, y)) q.append((x, y, a)) if 'G' in li: x, y = i, li.index('G') ghost.append((x, y)) if 'D' in li: x, y = i, li.index('D') exit.append(x) exit.append(y) array.append(li) #### test #### ghost_short = int...

틀리는 이유를 잘 모르겠습니다..

아래처럼 코드를 작성했는데, TC는 다 맞는데 제출하니 득점이 0이네요. 혹시 어느 부분이 잘못되었는지 아시는 분 계실까요? from collections import deque import sys input = sys.stdin.readline N, M = map(int, input().split()) board = [["."] * M for _ in range(N)] ghosts = [] for i in range(N): temp = input() for j in range(M): if temp[j] == "D": DY, DX = i, j elif temp[j] == "N": NY, NX = i, j elif temp[j] == "G": ghosts.append((i, j)) elif temp[j] == "#": board[i][j] = "#" else: continue def bfs(sy, sx, ey, ex, idx): # idx = 0이면 남우, 1이면 유령 globa...

총체적 난국 파이썬 코드

n, m = map(int, input().split()) maze = [list(input()) for _ in range(n)] def dfs(x, y): stack = [(x, y, [])] # 좌표와 경로를 함께 저장 while stack: x, y, path = stack.pop(0) if 0 <= x < n and 0 <= y < m and maze[x][y] != "#" and maze[x][y] != "G": if maze[x][y] == "D": path.append((x,y)) short_path = path[1:] #path.append((x, y)) return short_path # 최단 경로 반환 if maze[x][y] != "N": maze[x][y] = "#" stack.append((x, y + 1, path + [(x, y)])) # 오른쪽 이동 stack.append((x, y - 1, path + [(x, y)])) # 왼쪽 이동 stack...

제출이력에서 제출한 기록이 안나와요

제출이력에서 제출한 기록이 안나와요 썸네일에서 틀렸다는 마크만 있을 뿐입니다 서버에 문제가 생겨서 맞았는데 틀렸다고 나온거겠죠? 하하

테스트케이스

#include <stdio.h> #include <stdlib.h> #include <math.h> #define STACK_SIZE 10000000 int bfs(char*** arr, int n, int m); char stack[STACK_SIZE][3] = {0,}; char goal[2] = {0,}; char temp[STACK_SIZE][2] = {0,}; int main(void) { char ***grid; int n,m; scanf("%d %d",&n, &m); grid = (char***)malloc(sizeof(char**)*n); for(int i=0; i<n; i++) { grid[i] = (char**)malloc(sizeof(char*)*m); for(int j=0; j<m; j++) { grid[i...