[질문] 백준) 힌트 부탁드립니다..

[차룬]

https://www.acmicpc.net/problem/1325

저는 bfs를 사용했습니다.

A가 B을 신뢰할 때  B -> A 방향 그래프를 만들고

모든 노드에 bfs을 돌려서 가장 많이 연결된 노드를 순차적으로 출력했습니다.

아래 코드는 시간초과가 납니다....

어디서 접근해야할지 모르겠습니다.

https://ideone.com/qD92rB

[차룬]

ideone 코드 루리웹 글에서 바로 볼 수 있나요?

[차룬]

script 태그가 안 되네요..

[_ Bolic]

루리웹에 안되는 기능이 많아요 ;ㅅ; 수식 넣기도 힘들고요
백준 문제번호 알려주실 수 있나요?

[차룬]

본문 수정했습니다!

[_ Bolic]

대부분 잘 짜셨는데, 문제 1개가 있네요.
시작점 n을 기준으로 탐색을 하는데, 탐색할때마다 visited를 초기화합니다. 이것때문에 TLE가 나겠네요.
예를 들어서 1->2->..->n->1이라는 크기 n짜리 cycle을 생각합시다. 1부터 시작하면 n번 탐색할것이고, 2부터 시작하면 또 n번 탐색하겠죠. n부터 시작해도 n번 탐색할것이고요.
결국 O(n^2)의 연산이 필요해서 시간초과를 받게 됩니다.

그래서, visited 배열은 n을 받을때마다 초기화를 하면 안됩니다.
다음과 같은 방식을 생각해봅시다.

visited 배열을 bool로 선언하지 말고, int로 선언합시다.
그리고 다음과 같이 탐색하는데,

만약 visited==0이라면 완전히 탐색하지 않은 정점, -1이라면 탐색중인 정점, 그 이외에는 탐색이 끝난 정점이고, "이 정점부터 시작하면 총 visited개의 정점을 방문할 수 있다"라고 합시다.

이제 queue에서 빼내면서 탐색할때, visited[next]==0이라면 visited[next]=-1로 바꾸어주고 계속 탐색합시다.
만약 visited[next]==-1이라면 현재 탐색중인 node를 만났으므로, 기존과 비슷하게 더이상 탐색하지 않고 거기서 종료합시다.
탐색을 종료할 때, next부터 시작해서 몇개를 방문할 수 있는지 알아야 합니다.
이는 현재 next에 방문했을 시점 - 처음 next에 방문했을 시점이 됩니다.
그리고 방문한 정점을 되돌아가면서, visited를 마저 갱신해주면 됩니다. 이 과정을 위해서 BFS가 아닌 DFS가 필요합니다.

[_ Bolic]

예를 들어서 1->2->3->4->3 이라는 그래프를 생각하고, 정점 2에서 탐색을 시작한다고 봅시다.
visited[2]==0이기 때문에, visited[2]==-1로 체크를 해주고, visited[3]을 탐색해줍니다.
visited[3]==0이기 때문에, visited[3]==-1로 체크를 해주고, visited[4]을 탐색해줍니다.
visited[4]==0이기 때문에, visited[4]==-1로 체크를 해주고, visited[3]을 탐색해야 하는데, 이것은 이미 -1이라는 값이 존재하죠.
-1을 만나는 순간 "이미 탐색중인 정점을 만나게 되었으므로" 더이상 탐색을 하지 않고 visited의 최종값을 갱신해주면 됩니다. 이 탐색중인 정점 이름을 p라고 합시다(여기서는 p=정점 3이 되겠죠)
p를 처음 방문할 시점은 두번째이고(2다음 3을 보죠), 두번째로 방문할 시점은 4이기 때문에(2,3,4다음 3을 보죠) visited[4]=4-2=2로 설정한 후 탐색을 종료합니다.

이제 DFS를 했으니 정점을 반대로 보겠죠?
4번 정점 탐색을 완료했으니 이제 3번 정점으로 다시 돌아가게 됩니다.
만약 visited[p]값이 양수로 확정된 상태라면, visited[현재]=visited[다음]+1로, 아니면 visited[현재]=vistied[다음]으로 설정해줍니다.

현재 정점 3을 보고 있는데, 아직 visited[p](=visited[3])의 값이 -1인 상태이므로, visited[3]=visited[4]=2로 설정하고, 탐색을 종료합니다.
그러면 다시 정점 2로 되돌아갑니다. visited[3]의 값이 양수로 정의되어 있는 상태이므로, visited[2]=visited[3]+1=3으로 설정해둡니다.
이제 더이상 탐색을 종료할 노드가 없으므로 끝납니다.

[_ Bolic]

이제 visited 배열을 보면 [0,3,2,2]로 되어있을것입니다. visited[v]==0인 v가 있다면, 아직 탐색이 안되었다는 뜻이므로 그러한 정점을 다시 찾아서 탐색을 반복해줍니다.

정점 1에서 부터 다시 시작한다고 봅시다. next=2라서 2번째 정점을 봐야 하는데, 이번에는 visited[next]==-1이 아닌, visited[next]==c라는 어떠한 양수값이 존재하는 상태를 마주하게 됩니다.
이 경우는 visited[p]값이 이미 양수로 확정된 상태로 간주하고, 갱신하면 됩니다. 즉, visited[1] = visited[2]+1 = 4로 설정하고 바로 탐색을 종료하면 됩니다.

그러면 이제 visited 배열은 [4,3,2,2]가 되겠죠? 더이상 0인 node가 없으므로 여기서 종료하면 됩니다.
이렇게 탐색할때마다 visited 배열을 초기화 하지 않아야 빠르게 답을 구할 수 있습니다.
visited 배열을 초기화 하지 않으면 풀이가 조금 복잡하죠, 하지만 어쩔수 없습니다 ;ㅅ;

[차룬]

상세한 설명 감사합니다.
빨리 해결해서 자랑?하고 싶지만 쉽게 해결되지 않네요...
보니까 데이터셋 변경 후 자바는 시간이 빡빡해서 기존에 정답코드들도 틀림처리 되었더군요ㅜㅜ
조금 더 머리 굴려보겠습니다.

[팬더쒸]

혹시 해결하셨나요?

일단 StringBuilder는 delete대신에 setLength(0) 를 쓰는게 삭제 과정을 거치지 않아서 좋아요

그리고 윗분처럼 방문 여부는 for문 바깥에 int 배열로 선언하는 게 좋아요
방문 배열을 visited, 현재 for문의 회차 수를 n, 큐에서 다음 확인할 위치를 p라고 하면
visited[p]!=n 일 경우, 현재 회차에서 방문하지 않는 위치란 의미가 돼요
이런 식으로 쓰면 배열을 매 회차마다 새로 선언하지 않아도 돼서 메모리도 적게 먹고, 초기화를 하지 않아도 돼서 성능도 올라가요