소프티어

python 그리디하게 풀어봤습니다. 유령최소거리보다, 남우 최소거리가 짧다면 YES

#결국 문제를 쉽게푸는 핵심은 중간에 고스트를 만나서 실패하게될 것을 따지기보단, 결과만을 봤을때 어차피 고스트가 더 거리가 짧다면 이길 수 없는 게임 인것을 인지해야함. import sys from collections import deque #그리고 고스트가 있는경우 고스트의 골인지점 최단거리와 남우 골인지점 최단거리를 비교했을때 #고스트가 민우보다 더 짧은거리면, 민우 패배 #고스트 최단거리는 도착지점(x,y)와 고스트 지점(a,b)를 통해 abs(x-a)+abs(y-b)로 구할수있음. #민우최단거리는 bfs를 써야함. def ghost_min_dist(start,end): return abs(start[0]-end[0])+abs(start[1]-end[1]) def bfs(grid,start,end): row,col=len(grid),len(grid[0]) visited=set() queue=deque([(start[0],start[1],0)])# x , y , 거리 d...

동시에 도착하는 경우 처리 방법

import sys from collections import deque dirs = [(0,1),(1,0),(0,-1),(-1,0)] n, m = map(int, sys.stdin.readline().split()) maps = [list(sys.stdin.readline().strip()) for _ in range(n)] queue = deque() nv = [[False] * m for _ in range(n)] gv = [[False] * m for _ in range(n)] for i in range(n): for j in range(m): if maps[i][j] == 'N': queue.append((i, j, 'N')) nv[i][j] = True elif maps[i][j] == 'G': queue.append((i, j, 'G')) gv[i][j] = True def bfs(): while queue: x, y, who = queue.popleft() for...

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...