전체 글 (11) 썸네일형 리스트형 [리트코드 17] DFS 탐색 문제풀이2 DFS 탐색(깊이 우선 탐색) 알고리즘은 대표적인 그래프 탐색 방법 중 하나로 모든 노드를 방문(전체 탐색)해야하는 경우 BFS(너비 우선 탐색)에 비해 간단하게 풀이가 가능하여 선호되는 방식이다. 아래 문제의 경우도 모든 번호의 조합을 찾아야 함으로 DFS 방법으로 풀이할 예정이다. 17. 전화 번호 문자 조합 (Letter Combinations of a Phone Number) Example 주어진 2~9 사이의 숫자를 포함하는 문자열의 숫자가 나타낼 수 있는 가능한 모든 문자 조합을 출력하라. (단, 1은 어떤 문자도 매핑되어있지 않다.) 예를 들어 "23" 의 입력값이 주어졌을 때 2는 abc 의 문자 출력이 가능하고 3은 def 문자 출력이 가능하므로 각각 한 문자씩 조합을 해보면 총 9개의 .. [리트코드 200] DFS 탐색 문제풀이1 *DFS란? Depth-first search의 약자로 깊이 우선 탐색하는 그래프 탐색 방법 중 하나이다. 자세한 내용은 [자료구조] 그래프(Graph) 참고. 200. 섬의 개수 (Number of Islands) Example - 주어진 2D 그리드 맵(m*n)에서 '1' 은 땅을 '0'은 물로 표현했을 때 섬의 개수를 출력하라. Constraints - m == grid.length - n == grid[i].length - 1 = m or j = n or grid[i][j] != '1': return # 탐색 여부 마킹 gri.. [자료구조] 그래프(Graph) 이전 포스트의 트리(Tree) 자료 구조는 그래프의 한 종류이다. 하지만 모든 그래프가 트리는 아니다. 그래프(Graph) - 노드와 그 노드를 연결하는 간선(edge)를 하나로 모아 놓은 것이다. - 사이클(cycle)이 존재할 수도 있고 존재하지 않을 수도 있다. 사이클이 없는 그래프를 비순환 그래프(acyclic graph) 라고 부른다. - 방향성이 있을 수도 있고 없을 수도 있다. 그래프 표현 방법 1. 인접 리스트(Adjacency list) - 그래프를 표현할 때 사용되는 가장 일반적인 방법이다. - 아래 그래프를 인접 리스트로 표현하면 다음과 같다. adj[0]: 1 adj[1]: 2 adj[2]: 0, 3 adj[3]: 2 2. 인접 행렬(Adjacency matrix) - N*N boo.. 이전 1 2 3 4 다음
