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..
}