park780172   4년 전

계속 생각해봐도

dfs에서 어디가 잘못 됐는지

반례가 무엇인지

찾기가 어렵네요..

한 정점으로부터 거리가 2인 정점들의 개수 중 최댓값을 찾는 문제라고 이해했는데

제 코드에서 어디가 무엇이 잘못 됐는지 잘 모르겠습니다!

meringueee   4년 전

일단 본 문제 굳이 DFS로 푸시면 다소 비효율적이구요,

그냥 2중FOR문 돌리시거나

플로이드 워셜 돌려서, 각 줄에서 최단거리 2 이하인 정점 갯수 구하시는 것도 나쁘지 않네요.

일단 이 경우에 각각의 사람에 대해 dfs를 한 번씩 돌려주는 것 같은데요,

A-B가 친구면 지금 A/O 노드로 시작을 하는데, 두 번 이동하며 A가 TRUE로 찍힐 수도 있을 것 같아요.

일단 간단하게 코드만 보고 답변드리는 거라... 시도해본 예시 알려주시면 더 도와드릴 수 있을 것 같네요

park780172   4년 전

@meringueee


우선 댓글 감사합니다.

플로이드-와샬로 한 번 해보겠습니다.

그런데, 제가 생각한 dfs에서 어떤 잘못이 있는지 몰라 질문하게 됐습니다.(잘못된 부분을 알고싶어서 질문하였습니다.)

말씀하신

'A-B가 친구면 지금 A/O 노드로 시작을 하는데, 두 번 이동하며 A가 TRUE로 찍힐 수도 있을 것 같아요.'

이 부분이 잘 이해가 되지 않습니다.

사실 A/O 노드가 어떤 의미인지 잘 모르겠습니다. 두 번 이동의 의미도 잘 모르겠습니다. 

제가 사용한 테스트 케이스는 기억나는 것들로 아래에 올려봅니다.

6
NNNYNN
NNYNNY
NYNYNN
YNYNYN
NNNYNN
NYNNNN
5

5
NYYNN
YNYNN
YYNYN
NNYNY
NNNYN

7
NYNYYYY
YNNNYNN
NNNYNNN
YNYNNNN
YYNNNYY
YNNNYNN
YNNNYNN
6

2
NN
NN
0

2
NY
YN
1

1
N
0

park780172   4년 전

두 번째 테스트 케이스의 답은 제 코드 기준으로 4로 나옵니다.

5
NYYNN
YNYNN
YYNYN
NNYNY
NNNYN
4

meringueee   4년 전

6

NYYNYN

YNYNNN

YYNYNN

NNYNNN

YNNNNY

NNNNYN


정답은 5인데 아마 4가 나오지 않을까 싶네요.

park780172   4년 전

@meringueee

아 감사합니다.

0에서 출발했을 때, 3까지 가야하는데 이미 2에서 방문처리 되버려서 0->2->3을 못 가는군요.

반례 감사합니다.

이 문제 같은 경우 dfs로 풀기에는 살짝 좀 그렇긴 하겠네요.

meringueee   4년 전

네네 바로보셨습니다~

DFS로 꼭 풀어보고 싶으시다면, 2-친구 수를 바로 반환하지 않고

input처럼 2차원 배열로 2-친구를 표시하여 진행한 다음

차후에 2-친구 수를 각각 구하는 방법으로 하면 반례에 대응할 수 있지 않을까 싶습니다.

park780172   4년 전

@meringueee

혹시 몰라서 bfs로 푸니 바로 풀리네요 ..

dfs로는 좀 더 생각을 해봐야할 것 같아요.

dfs는 방문 처리가 무조건 있어야 될 것 같아서 어쩔 수 없는 부분인 것 같기도 하네요.

여하튼 반례와 설명 다시 한 번 정말 감사합니다!

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