개발자 톡
연습문제 톡
[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회_정기_코딩_인증평가_기출]_출퇴근길