16947번 - 서울 지하철 2호선
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인 곳을 방문하면 그 때의 거리를 반환하도록 했습니다. 혹시 어디가 문제인지 알려주시면 감사하겠습니다 ㅠㅠ..
저도 예제는 맞는데 바로 틀렸다고 뜨네요,,
댓글을 작성하려면 로그인해야 합니다.
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인 곳을 방문하면 그 때의 거리를 반환하도록 했습니다. 혹시 어디가 문제인지 알려주시면 감사하겠습니다 ㅠㅠ..