구르는 돌에는 이끼가 끼지 않는다

www.acmicpc.net/problem/1260

dfs와 bfs를 이해하기에 정말 좋은 문제였다. 

문제의 핵심은 각 알고리즘을 이해하고 이를 구현하는 방법을 이해 하는것이었다. 

dfs = stack 이고, 크게 재귀함수를 이용하거나, java에서 제공하는 stack 컬렉션을 사용한다. 

일반적으로는 재귀를 쓰는 것이 코드가 깔끔하여 재귀를 많이 쓴다. 

bfs = queue 이고, queue는 보통 java에서 제공하는 queue 인터페이스 사용하여 많이 사용한다. 

package com.ji.beakjoon;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class DfsAndBfs02 {
	
	static int nodeNum, edgeNum, startNode;
	static int[][] graph;
	static boolean[] DFSisVisited, BFSisVisited;
	static ArrayList<Integer> DFSvisitArr, BFSvisitArr ;
	static Queue<Integer> queue;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		nodeNum = sc.nextInt(); // 점갯수
		edgeNum = sc.nextInt(); // 선갯수
		startNode = sc.nextInt(); // 시작노드
		graph = new int[nodeNum + 1][nodeNum +1];
		
		DFSisVisited = new boolean[nodeNum +1];
		BFSisVisited = new boolean[nodeNum +1];
		DFSvisitArr = new ArrayList();
		BFSvisitArr = new ArrayList();
		queue = new LinkedList<Integer>();
		
		for( int i = 0 ; i < edgeNum ; i++ ) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			graph[a][b] = 1;
			graph[b][a] = 1;
		}
		
		for( int i = 0 ; i < nodeNum+1 ; i++) {
			DFSisVisited[i] = false;
			BFSisVisited[i] = false;
		}
		
		dfs(startNode);
		bfs(startNode);

		for( int i = 0 ; i < DFSvisitArr.size() ; i++ ) {
			System.out.print(DFSvisitArr.get(i) + " ");
		}
		System.out.println();
		for( int i = 0 ; i < BFSvisitArr.size() ; i++ ) {
			System.out.print(BFSvisitArr.get(i) + " ");
		}

	}
	
	static void bfs(int node) {
		// 방문한 노드 처리
		BFSisVisited[node] = true;
		// 방문한 노드 번호 리스트 저장
		BFSvisitArr.add(node);
		for( int i = 1 ; i <= nodeNum ; i++) {
			//간선이면서, 방문한 노드가 아니고, 검색해야할 노드 큐에 저장해준다.
			if( graph[node][i] == 1 && BFSisVisited[i] == false && queue.contains(i)==false) {
				queue.add(i);
			}
		}
		
		//검색 큐가 비어있지 않으면 검색 큐에서 삭제해준 후 제 검색
		if(!queue.isEmpty())
			bfs(queue.poll());
	}
	
	static void dfs(int node) {
		//방문한 노드 번호에 대한 boolean 처리
		DFSisVisited[node] = true;
		//방문한 순서에 대한 노드 정보 리스트 저장
		DFSvisitArr.add(node);
		for( int i = 1 ; i <= nodeNum ; i++ ) {
			if(graph[node][i] == 1 && DFSisVisited[i] == false) {
				dfs(i);
			}
		}
	}

}

programmers.co.kr/learn/courses/30/lessons/42839

소수 찾기의 핵심은 숫자를 입력했을 때 나올 수 있는 조합의 수를 찾아 내는 것이다.

보통 이러한 경우의 수를 추출 해야할 때는 완전 탐색 알고리즘인 DFS를 많이 쓰게된다. 

DFS(Depth First Search)로 깊이 우선 탐색이라고 한다. 

노드와 간선으로 구성된 트리이다. 

여기서 DFS는 트리를 탐색하는 방법 중에 하나인데 이와 상반대는 개념은 BFS가 있다. 

앞으로 코테를 볼경우 이와 같이 경우의 수를 추출해야하는 경우에는 DFS가 떠오르고 코드를 작성할 수 있는 연습을 많이 해야할 듯 하다. 

특히, DFS는 스택을 활용하기 때문에 점화식과 탈출식을 잘 생각해야 할 듯하다. 

DFS와 관련된 많은 문제를 통해서 문제에 익숙해지는 노력을 해야겠다.

다음은 내가 풀었던 방식이다. 

[해결]

1) 입력된 문자열이 만들수 있는 경우의 수를 구한다.

저의 경우는 dfs를 이용해서 발생할 수 있는 경우의 수를 뽑아냈습니다.

2) 소수 여부를 판단해서 count를 한다.

package com.ji.study;

import static org.junit.Assert.assertEquals;
import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.Test;

class FindPrimeTest {

	@Test
	void test() {
		
		Solution_42839 test = new Solution_42839();
		
		assertEquals(3, test.solution("17"));
		assertEquals(2, test.solution("011"));
		assertEquals(1, test.solution("2"));
		assertEquals(12, test.solution("7843"));
		assertEquals(0, test.solution("9999999"));
		assertEquals(1336, test.solution("1276543"));
		
	}

}

package com.ji.study;

import java.util.ArrayList;
import java.util.List;

public class FindPrime {

	/**
	 * 소수는 1과 자기 자신으로만 나누어지는 수임
	 * 
	 * @param args
	 */
	public static void main(String[] args) {

		String input = "1276543";
		System.out.println(solution(input));

	}

	public static int solution(String numbers) {
		int answer = 0;

		// 숫자 조합 저장 리스트
		List<Integer> makeNumber = new ArrayList<Integer>();
		List<Integer> onlyNumber = new ArrayList<Integer>();

		// input 숫자 초기화
		char[] numToArr = numbers.toCharArray();
		Integer len = numToArr.length;

		// dfs를 이용한 입력된 숫자가 조합할 수 있는 모든 경우의 수 저장
		dfs(0, initNodeValue(numToArr, len), new int[len], new boolean[len], makeNumber);

		// 중복 숫자 제거
		for (Integer num : makeNumber) {
			if (!onlyNumber.contains(num))
				onlyNumber.add(num);
		}

		// 소수인 경우
		for (Integer num : onlyNumber) {
			if (isPrimeNumber(num))
				answer++;
		}

		return answer;
	}

	public static int[] initNodeValue(char[] numToArr, Integer numLength) {
		int[] result = new int[numLength];
		for (int i = 0; i < numLength; i++) {
			String numStr = String.valueOf(numToArr[i]);
			result[i] = Integer.valueOf(numStr);
		}
		return result;
	}

	public static void dfs(int n, int[] arr, int[] result, boolean[] visit, List<Integer> makeNumber) {
		if (n == arr.length) {// 입력된 숫자 길이 만큼의 경우의 숫자들

			// 모든 경우의 숫자들에서 한자리씩 감소하는 경우의 숫자 예외 처리
			int resultLength = result.length;
			while (resultLength > 0) {
				String numStr = "";
				for (int i = 0; i < resultLength; i++) {
					numStr += result[i];
				}

				if (numStr != "")
					makeNumber.add(Integer.valueOf(numStr));

				resultLength--;
			}

		} else {

			for (int i = 0; i < arr.length; i++) {
				if (!visit[i]) {
					visit[i] = true;
					result[n] = arr[i];
					dfs(n + 1, arr, result, visit, makeNumber);
					visit[i] = false;
				}
			}

		}
	}

	public static boolean isPrimeNumber(int number) {
		boolean result = true;

		if (number == 1 || number == 0)
			return false;

		for (int i = 2; i < number; i++) {
			if (number % i == 0) { // 나누어 떨어지는 지 확인
				result = false;
				break;
			}
		}
		return result;
	}

}