개발자 톡

연습문제 톡 [HSAT 6회 정기 코딩 인증평가 기출] 출퇴근길

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

등록일
2024-10-30 01:31:33
조회수
45
작성자
candysmh
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<int[]>[] adj2 = new ArrayList[n+1];

     

    for(int i=0; i<n+1; i++){

      adj[i] = new ArrayList<>();

      adj2[i] = new ArrayList<>();

    }

    for(int i=0; i<m; i++){

      st = new StringTokenizer(br.readLine());

      int x = Integer.parseInt(st.nextToken());

      int y = Integer.parseInt(st.nextToken());

      adj[x].add(new int[]{y,0});

      adj2[x].add(new int[]{y,0});

    }

    st = new StringTokenizer(br.readLine());

    int S = Integer.parseInt(st.nextToken());

    int T = Integer.parseInt(st.nextToken());

    dfs(S,T,canS, adj);

    dfs(T,S,canT, adj2);

    int ans =0;

    for(int i=1; i<n+1; i++){

      if(i!=S && i!=T && canS[i]==1 && canT[i]==1) ans++;

    }

    System.out.println(ans);

     

  }

  static int dfs(int s, int t, int[] can, List<int[]>[] adj){

    if(s==t || can[s]==1){

      return 1;

    }

    int ch=0;

    for(int[] arr: adj[s]){

      if(arr[1]==1) continue;

      arr[1]=1;


      int r = dfs(arr[0],t,can,adj);

       

       

      if(r==1){

        can[arr[0]]=1;

        can[s]=1;

        ch = 1;

      }

    }

    if(ch==1) return 1;

    else return 0;

  }

}



#[HSAT_6회_정기_코딩_인증평가_기출]_출퇴근길

이 카테고리의 톡 더보기