깊이 우선 탐색(DFS: Depth-First Search) 및 프로그래머스(모음사전)

💡 오늘의 학습 키워드

- 깊이 우선 탐색(DFS: Depth-First Search)
- 프로그래머스
    * 모음사전 : 미들러 문제(Level 2)

 

깊이 우선 탐색(DFS: Depth-First Search)

: 한 정점으로부터 시작하여 가능한한 깊이까지 탐색을 진행하고, 더 이상 진행할 수 없는 경우 다음 경로로 되돌아가는 방식이다. 이를 통해 미로 찾기와 같은 문제를 해결할 수 있다.

• 재귀 또는 스택을 활용해 구현 가능
• 깊이 우선 탐색
• 비순환 그래프에서는 모든 노드를 방문 가능
• 순환 그래프에서는 무한 루프에 빠질 수 있으므로, 이미 방문한 노드를 추적하여 방문하지 않도록 주의
• 스택의 용량에 따라 메모리 사용량이 증가

public class Main {

	// 방문처리에 사용 할 배열선언
	static boolean[] vistied = new boolean[9];
	
	// 그림예시 그래프의 연결상태를 2차원 배열로 표현
	// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
	static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	public static void main(String[] args) {
		dfs(1);
	}
	
	static void dfs(int nodeIndex) {
		// 방문 처리
		vistied[nodeIndex] = true;
		
		// 방문 노드 출력
		System.out.print(nodeIndex + " -> ");
		
		// 방문한 노드에 인접한 노드 찾기
		for (int node : graph[nodeIndex]) {
			// 인접한 노드가 방문한 적이 없다면 DFS 수행
			if(!vistied[node]) {
				dfs(node);
			}
		}
	}
}

 

* 코드 참고 사이트

[Algorithm] DFS (Depth-first Search)를 Java로 구현해보자!

 

---

 

오늘의 회고

문제1  : [모음사전]

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

문자 'A', 'E', 'I', 'O', 'U'만 존재하는 문자열이 있을 때, 입력받은 문자열은 몇 번째 순서인지 출력하는 문제였다.

 

처음에는 순서가 어떻게 증가되는지 다 방법을 알아볼까 싶었지만, 

그렇게 하면 시간낭비가 크고 제대로된 공부가 되지 않을 것 같아서 30분의 시간을 정해두고 다시 해결방법을 찾았다.

하지만, 30분이 지나도 해결방안을 찾지 못해 다른사람들의 풀이를 찾아봤다.

찾아본 결과 대부분이 dfs를 사용해서 풀이했다. 

 

프로그래머스

 

• 어떻게 해결했는지(다른사람의 풀이1)

class Solution {
	
    static int idx = 0;
    static int answer = -1;
	
    public int solution(String word) {   	
        dfs(word, "");        
        return answer;
    }
    
    public void dfs(String word, String text) {
    	if(answer > 0) return;
    	if(word.equals(text)) {
    		answer=idx;
    	}
    	idx++;
    	if(text.length()==5) {    		
    		return;
    	}
    	
    	dfs(word, text+"A");
    	dfs(word, text+"E");
    	dfs(word, text+"I");
    	dfs(word, text+"O");
    	dfs(word, text+"U");
    }

}

 

 

* 코드 참고 사이트

[Java] 모음사전 - Lv2 프로그래머스 완전탐색 / 코딩테스트 고득점 Kit

 

• 무엇을 새롭게 알았는지

오늘 우테캠 1차 코테를 참여했다가 비기너만 풀이해서는 진전이 없을 것 같아서 미들러 문제를 풀이하기 시작했다.

하지만 갑자기 비기너에서 미들러를 풀기에는 아직 부족한 점이 많았다.

각종 알고리즘과 자료구조의 개념에 대해 다시 배우고 이를 문제에 응용하는 걸 많은 문제를 풀이하며 배워야겠다고 생각했다. 특히나 문제 응용력이 많이 부족한 것 같다고 생각했다. 다시 배우며 정리해 나갈 생각이다...

지금보다 더 많은 노력이 필요할 것 같다.....

 

내일 학습할 것은 무엇인지 (최대 3개)

• 정보처리기사 실기
• 자바 형변환 정리
• DFS/BFS 정리
• 클럽99 코딩테스트(미들러)