dfs

개발만 하다가 오랜만에 알고리즘 문제를 풀었다. 문제를 2시간이나 풀었다..알고리즘 근육을 다시 좀 키워야할 필요성을 느꼈다. 풀이 전략 요약하자면 지도에서 땅(1) 과 바다(0) 가 주어진다. 상/하/좌/우 + 대각선 총 8방향으로 연결된 1들은 같은 섬으로 간주한다. 여러 개의 테스트케이스가 입력되고, w=0, h=0이면 종료한다. 각 테스트케이스마다 섬의 개수를 출력한다. 늘 그렇듯 흔히 하는 방식으로 먼저 static 변수를 생성해준다. 지도를 2차원 배열에 저장하고 방문 여부 체크, 전체 좌표 순회, 모든 좌표 탐색 후 개수 출력! 이렇게 접근했다. 연결된 땅(1)을 하나의 섬으로 세는 건 그래프 탐색 문제고 DFS를 써야 할지 BFS를 써야 할지 고민을 했는데 한 방향으로 깊게 들어..

문제 풀이 분석 1. 주어진 지도에서 연결된 집들을 하나의 단지로 본다. 2. 상하좌우로 연결된 집들을 하나의 단지로 취급한다. 3. 각 단지의 크기와 단지의 개수를 구한 후 단지의 크기를 오름차순으로 정렬한 후 출력한다. 풀이 전략 그래프 탐색 문제이다. DFS를 사용해서 집들 탐색하고 단지의 크기를 구하자. 방문 처리를 해서 이미 방문한 집은 다시 방문하지 말자. 모든 단지를 찾고 오름차순으로 정렬하고 출력하자. 코드 풀이 1. 입력과 배열 초기화 지도 크기 N을 입력받고 N x N 크기의 arr과 방문 여부를 판단하는 배열인 check를 초기화한다.arr배열에 0과 1로 이루어진 지도를 입력받는다.line.charAt(j) - '0'을 사용해서 문자를 숫자로 변환하고 저장한다. Buff..

문제 풀이 문제 이해하기 설명:주어진 그래프에서 DFS와 BFS 탐색 결과를 구하라.탐색 시 노드 번호가 작은 순서부터 방문한다.입력 조건:노드의 수, 간선의 수, 시작 노드를 입력해야 한다.간선은 양방향이다.출력 조건:DFS 결과와 BFS 결과를 출력한다. DFS와 BFS 간단 설명 DFS는 깊이 우선 탐색이며 한 노드를 방문한 후 그 노드와 연결된 노드를 재귀적으로 탐색한다. 재귀 호출 또는 스택을 사용하여 구현 가능하다. BFS는 너비 우선 탐색이며 한 노드를 방문한 후 연결된 모든 노드를 큐에 넣어 순차적으로 탐색한다. 큐를 사용하여 구현 가능하다. 코드 구조 입력 처리: 노드,간선 정보를 입력받아 인접 행렬을 생성한다. DFS 구현: 재귀 호출을 사용하여 깊이 우선으로 탐..

파이썬에서 스택과 큐는 모두 리스트로 구현한다.   스택(Stack) 자료구조 후입 선출 자료구조. ex) 총의 탄창, 급식판 등  스택은 뭔가를 쌓는다는 이미지를 떠올리면 된다. 파이썬에선 리스트를 활용하여 스택을 구현할 건데, 파이썬 리스트를 90도 회전해서 돌린 이미지를 상상하면 된다.   스택은 나중에 들어온 데이터가 먼저 빠져나가게 된다. 중요한 점은, 데이터의 삽입과 추출이 모두 리스트의 뒷부분에서 일어난다는 것이다. 신규 데이터의 삽입은 append()를 활용하며 데이터의 추출은 pop()을 활용하여 메서드로 자연스럽게 스택 자료구조를 구현할 수 있다. 예시 코드로 구현해보겠다.   ▶ 웹 서핑을 하다가 뒤로 가는 경우를 구현visits = [] # 방문 기록지#1. 처음으로 구글에 방문vi..