소프티어

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));
       StringTokenizer st = new StringTokenizer(br.readLine());
       int N = Integer.parseInt(st.nextToken());
       int M = Integer.parseInt(st.nextToken());
       Map<Integer,ArrayList<Integer>> map = new HashMap<>();
       //간선 정보 저장
       for(int m=0;m<M;m++){
          st = new StringTokenizer(br.readLine());
          int start = Integer.parseInt(st.nextToken());
          int end = Integer.parseInt(st.nextToken());
          //기존의 연결된 endpoints를 조회
          ArrayList<Integer> endPoints = map.getOrDefault(start,new ArrayList<>());
          //endPoint 추가
          endPoints.add(end);
          //map에 반영
          map.put(start,endPoints);
       }

       st = new StringTokenizer(br.readLine());
       int startPoint = Integer.parseInt(st.nextToken());
       int endPoint = Integer.parseInt(st.nextToken());
       int result =0;
       for(int n =1;n<=N;n++){
          boolean flag = false;
          if(n==startPoint || n ==endPoint){
             continue;
          }
          //startPoint -> n
          if(findPoint(startPoint,n,endPoint,N,map)){
             //n -> startPoint
             if(findPoint(n,endPoint,startPoint,N,map)){
                //endPoint -> n
                if(findPoint(endPoint,n,startPoint,N,map)){
                   // n -> endPoint
                   if(findPoint(n,startPoint,endPoint,N,map)){
                      flag = true;
                   }
                }
             }
          }
          if(flag){
             result++;
          }
       }
       System.out.println(result);
    }
    public static boolean findPoint(int start , int end, int anotherEnd , int N,Map<Integer,ArrayList<Integer>> map){
       boolean[] visited = new boolean[N+1];

       Queue<Integer> queue = new LinkedList<>();
       queue.add(start);
       visited[start] = true;
       while(!queue.isEmpty()){
          int city = queue.poll();
          if(map.getOrDefault(city,new ArrayList<>()).size()==0){
             continue;
          }
          //연결된 도시
          for(Integer cityNum : map.get(city)){
             //방문 여부 확인
             if(!visited[cityNum]){
                //출퇴근 목적지
                if(cityNum == anotherEnd){
                   continue;
                }
                if(cityNum==end){
                   return true;
                }
                queue.add(cityNum);
                visited[cityNum] = true;
             }
          }
       }
       return false;
    }

}