[알고리즘 2667] 발표 자료

박상준·2024년 7월 4일

알고리즘

목록 보기

2/7

문제 분석

주어진 지도에서 연결된 집의 모임 을 찾아 단지로 정의
각 단지에 번호를 붙이는 작업을 수행함.
연결된 집 이라는 것은
- 좌우상하로 인접한 집을 의미함.

해법

BFS 혹은 DFS 을 사용( 그래프 탐색 ) 하여 지도를 순회
- 1 이라는 집을 만나면 내부적으로 그래프 탐색을 시도하여 count 을 증대
- 방문처리도 해준다.

코드분석

사전 조건

상하 좌우에 대한 탐색 방향 지정

private static int[] DX = {0, 0, -1, 1};
private static int[] DY = {1, -1, 0, 0};

필요한 변수 선언

private static int[][] graph; // 지도

private static int N; // 지도 크기
private static boolean[][] visited; // 지도 방문 내역

정답 자료구조
```
Queue<Integer> answers = new PriorityQueue<>();
```
- 단지 내의 집을 오름차순으로 정렬하여 한 줄에 하나씩 출력하는 과정
  - 에서 착안하여 별도 정렬과정 제외를 위하여 우선순위 큐 사용

그래프 담기

for (int i = 0; i < N; i++) {
    graph[i] = Arrays.stream(br.readLine().split("")) // 한 줄에 대해 String 배열로 받아서 스트림화
                       .mapToInt(Integer::parseInt) // String 값이기에 전부 Integer 값으로 변경
                       .toArray(); // 해당 Integer 값을 배열화
}

bfs 유효성 검사 및 수행

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (visited[i][j] == false && graph[i][j] == 1) {
            answers.add(bfs(i, j));
        }
    }
}

visited[i][j] == false
- 방문 처리되지 않은 부분만 bfs 를 돌도록 한다.
graph[i][j] == 1
- 1 이여 순회하지 ㅇㅇ

bfs 함수 분석

 int count = 1;

단지 수를 카운트하기위한 변수
- 기본적으로 bfs 가 수행되면 일단 하나는 있다는 의미기에 1부터 시작한다.

visited[x][y] = true;

방문처리

Queue<Pair> q = new LinkedList<>();
q.add(new Pair(x, y));

LinkedList 는
```
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
```
- List 와 Deque 를 구현하는데, Deque 는 Queue 인터페이스를 구현한다.
- 기본적으로 큐 인터페이스를 구현하는 클래스이며, 큐의 기본적인 동작을 지원하기에 사용

BFS 돌아가는 과정

while (!q.isEmpty()) {
    Pair current = q.poll();
    int currentX = current.x;
    int currentY = current.y;
    
    for (int i = 0; i < 4; i++) {
        int nx = currentX + DX[i];
        int ny = currentY + DY[i];
        
        if (0 > nx || 0 > ny || nx >= N || ny >= N) {
            continue;
        }
        
        if (graph[nx][ny] == 0 || visited[nx][ny]) {
            continue;
        }
        
        q.add(new Pair(nx, ny));
        visited[nx][ny] = true;
        count++;
    }
}

우선순위 큐란?

정의

각 요소가 우선순위를 가지는 추상 자료형임.
높은 우선순위를 가진 요소가 낮은 우선순위를 가진 요소보다 먼저 처리됨.

기본적인 구조

힙 구조
- 이진 힙을 사용하여 구현됨.
  - 최대 힙
    - 부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리
      완전 이진 트리
      
      구조
      
      모든 레벨이 완전히 채워져 있다 ( 리프 레벨 제외 )
      
      리프 노드에서는 왼쪽부터 오른쪽 순서대로 채워진다.

들어가기 전에..

논리적으로 저런식으로 그려지지만, 실제로는 배열을 사용하여 구현된다.
- 부모 노드의 인덱스가 i 라면
- 왼쪽 자식노드는 2i
- 오른쪽 자식노드는 2i + 1
- 해당 노드에서 부모노드를 찾는 경우 i / 2
  
  라는 공식이 적용된다.

삽입의 경우
- 우선순위 큐에서 3, 8, 2, 5, 10 이 순서대로 삽입되는 경우로 생각해보자.
- 최대 힙의 기반
1. 3 삽입
  - 큐가 비어있기에 3을 루트 노드로 삽입
  - [0, 3]
2. 8 삽입
  - 8을 트리의 다음 위치 ( 3의 왼쪽 자식) 에 삽입
  - 8이 부모 노드보다 크기에 서로 위치를 교환시킴.
  - [0 3 8 ] →
  - [0, 8, 3]
3. 2 삽입
  - 2를 트리의 다음 위치(8의 오른쪽 자식) 에 삽입한다.
  - 2는 부모 노드(8) 보다 작아서 그대로 둔다.
  - [0, 8, 3, 2]
4. 5 삽입
  - 5를 트리의 다음 위치인 3의 왼쪽 자식으로 삽입한다
  - 5는 부모3보다 크기에 서로의 위치를 교체
  - [0, 8, 3, 2] → [0 8 3 2 5] → [0 8 5 2 3]
5. 10 삽입
- 이런식으로 큐에서 제일 앞 (인덱스1) 의 값을 poll 하는 경우 항상 우선순위가 높은 값을 뺄 수 있음.
그렇다면 poll 을 수행하는 경우에는 어떻게 항상 우선순위가 최대값을 계속적으로 유지할 수 있느냐?
- 초기상태에서 poll 이 수행되는 경우 루트 값을 제거한다.
- 이후에 마지막 요소 ( 배열구조상의 마지막 요소 ) 인 5 를 루트로 교체한다.
- 루트 값인 5 는 자식 값중에 큰 값은 8 과 자리를 교체
- 자리가 바뀐 5 는 이후에도 재귀적으로 자식값과 자신을 비교하여 계속적으로 자리를 교체한다.