소프티어

17, 18, 20, 21 번 문제만 오답입니다 ㅠ

계속해서 찾아보고 있지만, 혼자 힘으로 찾기 어려워 글을 남깁니다 ㅠ 17, 18, 20, 21번 문제가 계속해서 오답으로 체크되는데, 혹시 아시는 반례 있으시면 부탁드리겠습니다ㅠ 아니면 코드상 문제점이 어디인지 혹시 아실까요? #include "stdio.h" #include "iostream" #include "vector" #include "queue" using namespace std; #define MAX 1000 class cPosition { public: int row; int column; }; int n, m; char ch; char map[MAX][MAX] = { 0, }; int GhostMap[MAX][MAX] = { 0, }; int NamooMap[MAX][MAX] = { 0, }; queue<cPosition> qNamoo; queue<cPosition> qGhost; cPosition cDestination; int dr[] = {0, -1, ...

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

유령의 위치를 큐에 한번에 넣어 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...

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

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