rhacnddl   3년 전

DFS로 사이클을 구하고 BFS로 각 역에서 순환선까지의 거리를 구하는 식으로 풀었습니다. 예제는 다 올바르게 나오는 것 같은데 제출하면 바로 틀렸다고 나옵니다...

DFS(int x, int before, String str) 형태의 DFS입니다.

x : 현재 정점

before : 직전의 정점

next : 다음 방문할 정점

str : 방문해온 정점들을 저장하는 문자열

----------------------------------------------------------

정점을 방문할 때 마다 str에 Integer.toString(x) + " " 형태로 붙여줍니다. 예를 들어 1, 3, 5 정점을 방문했다면 str = "1 3 5"이 됩니다.

다음 방문할 정점을 탐색할 때 만약 (1) next != before이면서  (2) str에 해당 정점이 있다면 

str에서 그 숫자의 위치를 찾아 substring -> spilt(" ") 후 String[]에 담아줍니다.

결과적으로 String[] 안에는 사이클을 형성하는 정점들이 들어가있습니다.

따라서 boolean[] cycle에 해당 정점들을 true로 변경해줍니다. 즉 cycle[i] == true 이면 순환선에 포함된다는 뜻입니다.

BFS는 각 정점에서 출발해 cycle[x] == true인 곳을 방문하면 그 때의 거리를 반환하도록 했습니다. 혹시 어디가 문제인지 알려주시면 감사하겠습니다 ㅠㅠ..

dnjun2   2년 전

저도 예제는 맞는데 바로 틀렸다고 뜨네요,,

댓글을 작성하려면 로그인해야 합니다.