15886 내 선물을 받아줘 2

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

연결관계를 ArrayList 를 노드로 하고 노드가 어떤 노드와 연결되있는지 HashSet 에 저장함
HashSet 끼리 교집합이 있으면 연결된 것들이므로 인형이 하나 필요하게됨

위의 그림처럼 두개의 집합으로 나뉘게 되는데 어떤 노드가 어떤 노드와 연결되는지 파악하는 부분이 어려웠다. 양방향 연결이면 연결관계를 파악하기 쉬운데 단방향 연결이다 보니 어떤 노드들이 하나의 집합을 이루는지 파악하기 어려웠다

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args)throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        String input = br.readLine();
        char[] map = new char[N];
        for (int i = 0; i < N; i++) {
            map[i] = input.charAt(i);
        }

        boolean[] visit = new boolean[N];

        ArrayList<HashSet<Integer>> nodes = new ArrayList<>();

        for (int i = 0; i < N; i++) {

            nodes.add(new HashSet<Integer>());
            int cur = i;
            nodes.get(i).add(cur);
            visit[cur] = true;
            while(true){

                if (map[cur] == 'W') {
                    cur--;
                } else if (map[cur] == 'E') {
                    cur++;
                }

                if(visit[cur] == false){
                    visit[cur] = true;
                    nodes.get(i).add(cur);
                }else{
                    break;
                }

            }

            for(int j = 0; j < N; j++) {
                visit[j] = false;
            }
        }

        for(int j = 0; j < N; j++) {
            visit[j] = false;
        }


        int answer = 0;
        for (int i = 0; i < N; i++) {
            HashSet<Integer> node = nodes.get(i);
            if(visit[i] == true)
                continue;

            visit[i] = true;
            for (int j = 1; j < N; j++) {
                HashSet<Integer> next = nodes.get(j);

                if(visit[j] == true)
                    continue;

                for(Integer num : next){
                    if(node.contains(num)){
                        visit[j] = true;
                        break;
                    }
                }
            }
            answer++;
        }

        System.out.println(answer);
    }
}