[백준] 1058 친구 - BFS(너비우선탐색) + DFS(깊이우선탐색) + 플로이드–워셜(Floywd Warshall) JAVA

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

코드설명

BFS(너비우선탐색) + DFS(깊이우선탐색) + 플로이드–워셜(Floywd Warshall) 를 활용합니다.

 

문제에 대한 이해하는 것이 가장 어려웠습니다.

문제가 행렬로 주어져있습니다. 단순히, 직접 그래프로 그린뒤 관계 간선을 직접 그려보면, 어떻게 해야할지 눈에 보입니다.

 

이 문제의 경우, 각 친구를 방문하는 순서를 제어하는게 중요합니다.

예를 들어, 1번 친구가 2번 친구와 3번친구에게 연결된 상태입니다.

그리고 2번 친구와 3번 친구는 연결된 상태입니다.

3번친구와 4번 친구가 연결된 상태입니다.

 

이때, 중요점은 1번친구가 2번친구를 방문하고, 3번친구를 연속방문한다면, 3번친구는 방문처리되어 1번친구가 방문하지 못합니다. 하지만, 1번친구가 2번친구를 방문하고 3번친구를 방문한뒤, 2번친구와 연관된 3번친구로 이동한다면, 이미 친구인 관계이므로 방문하지 않습니다. 하지만 3번친구와 연관된 4번친구로 이동할 수 있으니 더 많은 친구 조합을 찾을 수 있는 것 이지요.

 

즉, 위의 로직에서 BFS를 통한다면 더 간단하게 구현할 수 있습니다.

만약 DFS로 한다면, 먼저 돌면서 방문처리를 하며 방문할 List를 만들고 다시 해당 List를 재귀함수로 호출하는 것과 같이 조금 복잡해집니다.

코드

BFS로 푼 정답코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, K, M;
    private static int answer = 0;
    private static char[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
     
        N = Integer.parseInt(st.nextToken());
        arr = new char[N][N];
        for(int i=0;i<N;i++) {
        	st = new StringTokenizer(br.readLine());
        	arr[i]  = st.nextToken().toCharArray();
		}
        
        for(int i=0;i<N; i++) {
			answer = Math.max(answer, BFS(i));
        }
        
        System.out.println(answer);
    }
    
    private static int BFS(int idx) {
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(idx));
    	boolean[] visited = new boolean[N];
    	visited[idx] = true;
    	
    	int depth = 0;
    	int cnt = 0;
    	while(depth < 2) {
    		int qSize = q.size();
    		for(int iteration = 0; iteration < qSize; iteration++) {
    			Node temp = q.poll();
    			for(int c = 0; c < N; c++) {
    				if( visited[c] == false && arr[temp.idx][c] == 'Y' ) {
    					cnt += 1;
    					q.offer(new Node(c));
    					visited[c] = true;
    				}
    			}
    		}
    		depth+=1;
    	}
    	return cnt;
    }
}
class Node{
	int idx;
	public Node(int idx) {
		this.idx = idx;
	}
}

 

 

처음에 DFS로 구현하고 틀린 코드입니다.

물론, DFS로도 구현이 가능합니다만.. 문제에 대한 이해가 어려웠습니다.

이 코드의 경우 HashSet에 이미 방문한 친구 조합을 넣습니다. 하지만, 모든 친구의 경우를 세지 못하는데요.

해당 에러 관련해서 가장 큰 도움을 받은 질문이 있습니다. (참고 : https://www.acmicpc.net/board/view/44710 )

6
NYYNYN
YNYNNN
YYNYNN
NNYNNN
YNNNNY
NNNNYN

위의 예제를 보면 아시겠지만, 0번친구는 (0-2) - (2-3) 으로 3번 친구와 2-친구가 될 수 있었지만, 

앞선, (0-1) - (1-2) 과정으로 인해 2번친구와 hashset에 이미 친구처리가 되고 그로인해 2번친구에게 친구탐색을 시도하지 못합니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, K, M;
    private static int answer = 0;
    private static char[][] arr;
    private static HashSet<Integer> hashset = new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
     
        N = Integer.parseInt(st.nextToken());
        arr = new char[N][N];
        for(int i=0;i<N;i++) {
        	st = new StringTokenizer(br.readLine());
        	arr[i]  = st.nextToken().toCharArray();
		}
        
        System.out.println(func());
    }
    
    public static int func() {
    	
    	//시작점.
    	for(int r = 0; r < N; r++) {
    		int friendCnt = 0;
    		
    		hashset.clear();
    		hashset.add(r);
    		for(int c = 0; c < N; c++) {
    			if(r == c) continue;
    			if(hashset.contains(c) == true) continue;
    			if(arr[r][c] == 'Y') {
    				friendCnt+= 1;
    				hashset.add(c);
    				//만약 1차로 친구를 찾았다면, 2-친구가 가능한지 확인해야 한다.
    				if( isSecondFriend(r, c) == true) {
    					friendCnt += 1;
    				}
    			}
    		}
    		
    		answer = Math.max(answer, friendCnt);
    	}
    	return answer;
    }
    
    //A와 C를 찾았으니, B가 C의 친구인지를 찾는다.
    public static boolean isSecondFriend(int AFriend, int CFriend) {
    	
    	for(int c = 0; c < N; c++) {
    		if(c == AFriend) continue;
    		if(hashset.contains(c) == true) continue;
    		if(arr[CFriend][c] == 'Y') {
    			hashset.add(c);
    			return true;
    		}
    	}
    	return false;
    }
    
}