프로그래머스 네트워크

DFS인지 BFS인지 헷갈린다. 배우면서 하려니 힘드네. Level3까지만 해야겠다. 남이 작성한 코드 그대로 쓰니 개판되는 듯 하고. 한 문제당 30분이라는데 도저히 못 풀듯.

20년전 배운 linked list, stack, queue를 다시 보니 내가 참 힘들게 살았다. 애고 모가지야.

import java.util.Stack;
import java.util.Arrays;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		Solution sol = new Solution();
		int[][] nodeMap = new int[3][3];
		nodeMap[0][0] = 1;
		nodeMap[0][1] = 1;
		nodeMap[0][2] = 0;
		nodeMap[1][0] = 1;
		nodeMap[1][1] = 1;
		nodeMap[1][2] = 0;
		nodeMap[2][0] = 0;
		nodeMap[2][1] = 0;
		nodeMap[2][2] = 1;

		sol.solution(3, nodeMap);

		System.out.println("여기");
	}// void main

} // Main

class Solution {
	public int solution(int n, int[][] nodeMap) {

		/*
		 * boolean[] nodeVisited = new boolean[3]; nodeVisited[0] = false;
		 * nodeVisited[1] = false; nodeVisited[2] = false;
		 * 
		 * int[] nodeVisitedInd = new int[3]; nodeVisitedInd[0] = 0; nodeVisitedInd[1] =
		 * 0; nodeVisitedInd[2] = 0; //테스트를 위해 임시로.. //기존 nodeMap을 보고 만들어줘야 됨
		 */
		int[] nodeVisitedInd = new int[nodeMap.length];
		for (int i = 0; i < nodeMap.length; i++)
			nodeVisitedInd[i] = 0;

		// 중복을 삭제하기 위해 만듦.
		TreeSet trimedNodeVisitedInd = new TreeSet();

		int answer = 0;
		boolean flag = false;
		int visitIndex = 1;
		for (int i = 0; i < nodeMap.length; i++) {

//		dfs(nodeMap, nodeVisited, 0, flag);
			System.out.println("**********************");
			System.out.println("제일 바깥쪽 외부 루프");
			System.out.println("visitIndex = " + visitIndex);
			System.out.println("**********************");

			dfs(nodeMap, nodeVisitedInd, i, flag, visitIndex);

			visitIndex++;

		}

		System.out.println("nodeVisitedInd는" + nodeVisitedInd[0] + nodeVisitedInd[1] + nodeVisitedInd[2]);
		for (int i = 0; i < nodeVisitedInd.length; i++) {
			trimedNodeVisitedInd.add(nodeVisitedInd[i]);
		}
		System.out.println("TreeSet 크기는" + trimedNodeVisitedInd.size());
		answer = trimedNodeVisitedInd.size();

		return answer;
	} // solutions

	public static void dfs(int[][] nodeMap, boolean[] nodeVisited, int startNode, boolean flag) {
		Stack<Integer> dfsStack = new Stack<>();
		dfsStack.push(startNode);
		nodeVisited[startNode] = true;
		System.out.println("node " + startNode + " is visited");

		while (!dfsStack.empty()) {
			flag = false;
			int tempNode = dfsStack.peek();
			for (int i = 0; i < nodeMap.length; i++) {
				System.out.println(tempNode + "에서 " + i + " 노드로 검색 시작");
				// 왼쪽에서 오른쪽으로 훑음..1이면 링크가 있음.
				if (nodeMap[tempNode][i] == 1 && !nodeVisited[i]) {
					dfsStack.push(i);
					nodeVisited[i] = true;
					System.out.println("node " + nodeMap[tempNode][i] + " is visited");
					System.out.println("dsfStack has " + Arrays.toString(dfsStack.toArray()));
					flag = true;
					break;

				}

				System.out.println(tempNode + "노드 에서 " + i + "확인");
				System.out.println("길이 없거나 이미 방문하여 생략");
				System.out.println("노드 " + i + "방문 결과는" + nodeVisited[i]);

			} // for loop
			if (!flag) {
				dfsStack.pop();
				System.out.println("pop 실행됨");

			} // if(!flag)

		} // while

	}// dsf..

	public static void dfs(int[][] nodeMap, int[] nodeVisited, int startNode, boolean flag, int visitIndex) {
		Stack<Integer> dfsStack = new Stack<>();
		// for 루프를 돌릴 경우, 재방문을 방지.
		// 조건에 따라 Stack에 push.
		if (nodeVisited[startNode] == 0) {
			dfsStack.push(startNode);
			nodeVisited[startNode] = visitIndex;
			System.out.println("\t****노드 방문****");
			System.out.println("\tnode " + startNode + " is visited");
			System.out.println("\t****노드 방문****");
		}

		while (!dfsStack.empty()) {
			flag = false;
			int tempNode = dfsStack.peek();
			for (int i = 0; i < nodeMap.length; i++) {
				System.out.println(tempNode + "에서 " + i + " 노드로 검색 시작");
				// 왼쪽에서 오른쪽으로 훑음..1이면 링크가 있음.
				if (nodeMap[tempNode][i] == 1 && nodeVisited[i] == 0) {
					dfsStack.push(i);
					nodeVisited[i] = visitIndex;
					System.out.println("\t****노드 방문****");
					System.out.println("\tnode " + i + " is visited");
					System.out.println("\t****노드 방문****");
					System.out.println("node " + nodeMap[tempNode][i] + " is visited");
					System.out.println("dsfStack has " + Arrays.toString(dfsStack.toArray()));
					System.out.println("nodeVisited[" + i + "]는 " + nodeVisited[i]);
					flag = true;
					break;

				}

				System.out.println(tempNode + "노드 에서 " + i + "확인");
				System.out.println("길이 없거나 이미 방문하여 생략");
				System.out.println("노드 " + i + "방문 결과는" + nodeVisited[i]);

			} // for loop
			if (!flag) {
				dfsStack.pop();
				System.out.println("pop 실행됨");

			} // if(!flag)

		} // while

	}// dsf..

}