소프티어

너무 혼란스럽습니다 (C++)

반례를 너무 못 찾겠어서 구글링했습니다. 근데 구글에서는 dfs를 네 번 돌리더라구요. S출발, T출발 뿐만 아니라 역방향 그래프를 만들어서 S까지 갈 수 있는 노드, T까지 갈 수 있는 노드를 구하기 위해서요.. 도대체 왜죠...? 상황은 이해 돼서 적절한 반례를 여러 가지 해 봤는데 답이 똑같이 나와요 구글 코드와 ... 6 10 1 2 2 6 3 1 1 4 4 1 4 5 5 4 5 6 6 5 6 3 1 6 (시도했던 반례입니다) 다른 반례를 찾을 수 있는 고수를 찾습니다.. 반례를 안 찾더라도 왜 역방향 그래프를 만들어서 dfs를 두 번 더 돌려야 하는지 설명해 주시면 감사하겠습니다.. #include<iostream> #include <queue> #include <algorithm> #include <cstring> #include <vector> using namespace std; vector<vector<int>> map; bool visited[100001]; ...

32번 테스트 케이스 부터 계속 오답이 납니다 . 예외나 문제점 알려주시면 감사하겠습니다.

#include<iostream> #include<algorithm> #include<vector> // #define DEBUG using namespace std; bool visit_list[200001]; bool is_sroop_list[200001]={0,}; bool is_troop_list[200001]={0,}; int order_list[200001]; vector<int> edge_list[200001]; int order =0; bool dfs(int current , bool* is_roop_list){ #ifdef DEBUG cout << "order : "<< order_list[current] << " current : "<< current << endl; cout << "order list : "; for (int i=0; i<10; i++){ cout << order_list[i]<< " "; } cout << endl; #endif if(ord...

반례 알려주시면 정말 감사하겠습니다. 도저히 왜 틀렸는지 모르겠어요 ㅠ

import java.io.*; import java.util.*; public class Main {   public static void main(String[] args) throws Exception {     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));     StringTokenizer st = new StringTokenizer(br.readLine());     int n = Integer.parseInt(st.nextToken());     int m = Integer.parseInt(st.nextToken());     int[] canS = new int[n+1];     int[] canT = new int[n+1];     List<int[]>[] adj = new ArrayList[n+1];     List<...

같은 코드에서 순서만 바꿨는데 메모리 초과가 발생하는 이유가 궁금합니다.

같은 코드에서 순서만 바꿨는데 위에 코드는 4가지 테스트 케이스에서 메모리초과가 발생하고 아래는 메모리초과가 발생하지 않습니다. 그 이유가 무엇인가요? #메모리 초과 발생 코드 import sys sys.setrecursionlimit(10**6) def DFS(now, visit, adj): if visit[now]==1: return else: visit[now]=1 for neighbor in adj[now]: DFS(neighbor, visit, adj) return n,m=map(int, input().split()) # 정점, 간선 adj=[[] for _ in range(n+1)] # 노드별 이동 가능한 노드들 정보 adjR=[[] for _ in range(n+1)] # adj_reverse for _ in range(m): ...

반례 알려주시면 정말 감사하겠습니다. 소프티어 유튜브 풀이 영상 보고 구현 해봤는데 통과가 안되서요 ㅠㅠ

import java.io.*; import java.util.*; public class Main {     static int N; // 정점의 갯수 static int M; // 간선의 갯수 static ArrayList<Integer>[] graph1; // 정순 static ArrayList<Integer>[] graph2; // 정순 static boolean[] visited1; // 정순 S출발 static boolean[] visited2; // 정순 T출발 static boolean[] visitedR1; // 역순 S출발 static boolean[] visitedR2; // 역순 T출발 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu...

왜 틀렸는지 모르겠어요 ㅠ

틀린 이유를 모르겠는데 한 번 봐주실 분 계신가요 ㅠㅠ ?! import java.util.*; public class Main {     static int n;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         n = sc.nextInt();         int m = sc.nextInt();         int[][] map = new int[n+1][n+1];         int[][] reverseMap = new int[n+1][n+1];         for(int i=0; i<m; i++){             int x = sc.nextInt();             int y = sc.nextInt();             map[x][y] = 1;       ...

BFS로 풀었는데, 틀렸습니다.. 반례를 모르겠네요 ㅜ

BFS로 풀었는데 틀렸네요 ㅜㅜ 혹시 bfs로는 풀 수 없는 문제인지 제가 생각하지 못한 반례가 있는 걸까요..?ㅠ 출발점과 도착점을 제외하고 다른 도시들을 n이라고 했을때, 출발점 -> n -> 도착점 , 도착점 -> n-> 출발점 이 가능한 경우를 count 합니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; import java.util.stream.Collectors; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeni...

[HSAT 6회][level3] 출퇴근길

아래 경우에 오답 케이스를 알 수 있을까요? 어느 부분이 잘못됐는지 못찾겠네요.. import sys from collections import deque n, m = map(int, input().split()) adj = [[] for _ in range(n + 1)] adj_reverse = [[] for _ in range(n + 1)] for _ in range(m) : a, b = map(int, input().split()) adj[a].append(b) adj_reverse[b].append(a) S, T = map(int, input().split()) visited_1 = [0] * (n + 1) visited_1_R = [0] * (n + 1) visited_2 = [0] * (n + 1) visited_2_R = [0] * (n + 1) def BFS(start, end, visited) : ...

출퇴근길 테스트케이스중 4개가 런타임에러 뜹니다 ㅜㅜ

풀이 영상 보고 풀었는데 어디가 문제인가요? import sys input = sys.stdin.readline sys.setrecursionlimit(10**9) def dfs(s,g,visit): if visit[s]==1: return visit[s]=1 for x in g[s]: dfs(x,g,visit) n,m = map(int,input().split()) graph=[[] for _ in range(n+1)] graph_r=[[] for _ in range(n+1)] for _ in range(m): a,b=map(int,input().split()) graph[a].append(b) graph_r[b].append(a) s,e = map(int,input().split()) s_in = [0]*(n+1) dfs(s,graph_r,s_in...

[HSAT 6차] 출퇴근길

import sys sys.setrecursionlimit = (10**6) answer = 0 n, m = map( int, input().split() ) adj = [ [] for _ in range(n+1) ] adjR = [ [] for _ in range(n+1) ] for i in range (m): start, end = map( int, input().split()) adj[start].append(end) adjR[end].append(start) x, y = map (int, input().split()) # 어떤 노드로부터 연결된 점을 따라 방문 가능한 노드를 찾는 함수 def dfs (now, adj, visited): if visited[now] == 1: return visited[now] = 1 for neighbor in adj[now]: ...