[TIL]2025.03.04

기 원·2025년 3월 4일
TIL

TIL - 2025.03.04

오늘 배운 것 개요

오늘은 백준 1012번 문제 풀이(DFS & BFS), 재귀 함수, 큐(Queue), 프로그래머스 문제 풀이를 진행

  • 백준 1012번 (유기농 배추) 문제를 DFS & BFS 방식으로 해결하며 그래프 탐색을 학습했다.
  • 재귀 함수의 개념과 활용을 이해하고, DFS에서 재귀가 어떻게 사용되는지 배웠다.
  • 큐(Queue)와 우선순위 큐(PriorityQueue) 를 학습하고, BFS에서 큐가 어떻게 사용되는지 살펴보았다.
  • 프로그래머스 알고리즘 문제 해결을 진행하며 Java의 기본적인 문법과 오류를 수정하는 방법을 익혔다.

상세 내용

1. 백준 1012번 - 유기농 배추 (DFS & BFS)

배추밭에서 인접한 배추가 하나의 군집을 이루며, 군집 개수를 구하는 문제.
DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)을 활용하여 해결할 수 있다.

재귀 함수의 개념과 활용

  • 자기 자신을 호출하는 함수
  • 기본 조건(Base Case)와 재귀 조건(Recursive Case) 필요
  • DFS(깊이 우선 탐색)에서 자주 사용
  • Base Case가 없으면 StackOverflowError 발생 가능
  • 후입선출(LIFO) 구조

재귀 함수의 장점과 단점

  1. 장점
    • 코드가 간결
    • 문제 해결이 직관적
    • DFS, 그래프 탐색, 분할 정복에 자주 사용
  2. 단점
    • 메모리 사용량이 많음(스택 메모리 사용)
    • 재귀 깊이가 깊어지면 StackOverflowError 발생
    • 실행 속도 느림

큐(Queue)의 개념

  • Queue란 FIFO(First in first out, 선입선출)방식의 자료구조
  1. 큐(Queue)의 주요 연산
연산설명
enqueue()데이터 삽입 (큐의 뒤쪽, Rear에 추가)
dequeue()데이터 삭제 (큐의 앞쪽, Front에서 제거)
peek()가장 앞(front)의 데이터를 확인 (제거 X)
isEmpty()큐가 비어 있는지 확인
  1. 큐(Queue)와 우선순위 큐(Priority Queue)
자료구조큐 (Queue)우선순위 큐 (PriorityQueue)
동작 방식FIFO(선입선출)작은 값이 먼저 나옴
삽입offer()offer()
삭제poll() (맨 앞 제거)poll() (우선순위 높은 값 제거)
사용 예시BFS, 작업 예약다익스트라 알고리즘
  1. 큐(Queue) vs 스택(Stack)
자료구조큐 (Queue)스택 (Stack)
동작 방식FIFO (선입선출)LIFO (후입선출)
삽입offer()push()
삭제poll() (맨 앞 제거)pop() (맨 위 제거)
사용 예시BFS, 작업 예약DFS, 실행 취소

✔ 큐는 BFS에서 사용 (가까운 노드부터 탐색)
✔ 스택은 DFS에서 사용 (깊은 곳부터 탐색)

DFS(Depth-First Search)를 사용한 풀이

static void DFS(int x, int y){
    visited[y][x] = true; // 방문 처리

    for(int i = 0; i < 4; i++){ //네 방향으로 탐색 진행
        int nx = x + dx[i]; // 이동할 x좌표
        int ny = y + dy[i]; // 이동할 y좌표

        if(nx >= 0 && ny >= 0 && nx < M && ny < N){ // 범위 내에 있는지 확인
            if(field[ny][nx] == 1 && !visited[ny][nx]){ // 배추가 있으며 방문하지 않았으면
                DFS(nx, ny); // 재귀 호출
            }
        }
    }
}

✔ 재귀를 이용한 깊이 우선 탐색(DFS)
✔ 방문한 노드는 visited[][]배열로 체크
✔ 범위를 초과하지 않도록 조건문 활용

1. 코드 분해

visited[y][x] = true; // 방문 처리
  • 현재 방문한 좌표 (x, y)를 방문 완료 상태로 변경
  • visited[][]배열을 사용하여 중복 방문 방지
  • 방문 처리를 하지 않을 시 무한 재귀 호출로 StackOverflowError발생

for(int i = 0; i < 4; i++){ // 네 방향으로 탐색
  • dx[] 와 dy[] 배열을 활용하여 상하좌우 이동
    - i=0 -> 위쪽 이동
    - i=1 -> 아래쪽 이동
    - i=2 -> 왼쪽 이동
    - i=3 -> 오른쪽 이동

int nx = x + dx[i]; // 이동할 x 좌표
int ny = y + dy[i]; // 이동할 y 좌표
  • 현재 좌표 (x, y)에서 dx[i], dy[i]값을 더하여 이동할 좌표 (nx, ny) 계산

if(nx >= 0 && ny >= 0 && nx < M && ny < N){ // 배열 범위 내에 있는지 확인
  • 이동할 좌표(nx, ny)가 배열 범위를 벗어나는지 확인

if(field[ny][nx] == 1 && !visited[ny][nx]){ // 배추가 있으며 방문하지 않았으면
  • 배추가 있는 곳(1)만 이동
  • 이미 방문한 곳visited[ny][nx] == true이라면 이동하지 않음

DFS(nx, ny); // 재귀 호출
  • 이동 했다면 DFS(nx, ny)를 호출하여 재귀적 탐색
  • 현재 위치에서 다음 이동 좌표로 계속해서 탐색
  • 재귀 호출이 끝나면 DFS호출이 종료되고, 이전 호출로 돌아감(백트래킹)

2. 코드 흐름 예시

M = 5, N = 5
배추 위치:
(1,1) (1,2) (2,2) (3,3) (4,3)

배추밭 배열(field[][])

0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
0 0 0 1 1
0 0 1 1 1

DFS 실행 흐름

  1. (0,2)에서 탐색 시작 → DFS(0, 2) 호출
    • 방문 처리 → visited[0][2] = true
    • 아래 (1, 2) 이동 → DFS(1, 2) 호출
  2. (1, 2)에서
    • 방문 처리 → visited[1][2] = true
    • 왼쪽 (1, 1) 이동 → DFS(1, 1) 호출
    • 오른쪽 (1, 3) 이동 → DFS(1, 3) 호출
  3. (1, 1)에서
    • 방문 처리 → visited[1][1] = true
    • 더 이상 이동할 곳 없음 → DFS 종료 후 이전 호출로 복귀 (1, 2)
  4. (1, 3)에서
    • 방문 처리 → visited[1][3] = true
    • 아래 (2, 2) 이동 → DFS(2, 2) 호출
  5. (2, 2)에서
    • 방문 처리 → visited[2][2] = true
    • 더 이상 이동할 곳 없음 → DFS 종료 후 이전 호출로 복귀 (1,3)
    • 첫 번째 군집 탐색 완료
  6. 새로운 배추 (3, 3)에서 DFS(3, 3) 호출
    • (3, 4), (4, 3), (4, 4) 순서로 이동
    • 두 번째 군집 탐색 완료

BFS를 사용한 풀이

static void BFS(int x, int y){
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{x, y}); // 시작 위치 추가
    visited[y][x] = true;

    while (!queue.isEmpty()){
        int[] pos = queue.poll();
        int cx = pos[0], cy = pos[1];

        for (int i = 0; i < 4; i++){
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if(nx >= 0 && ny >= 0 && nx < M && ny < N){
                if(field[ny][nx] == 1 && !visited[ny][nx]){
                    queue.offer(new int[]{nx, ny});
                    visited[ny][nx] = true;
                }
            }
        }
    }
}

✔ Queue를 사용하여 레벨별로 탐색
✔ DFS보다 재귀 호출이 없어 안정적
✔ 최단 거리 탐색과 유사한 방식

1. 코드 분해

Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y}); // 시작 위치 추가
visited[y][x] = true; // 방문 처리
  • Queue를 선언, BFS 탐색 수행 준비
  • queue.offer(new int[]{x, y})를 통해 탐색을 시작할 좌표 (x, y)를 큐에 추가
  • visited[y][x] = true를 설정해 중복 방문 방지
  • BFS는 DFS와 달리 스택 대신 큐를 사용하며, 선입선출 방식으로 탐색 진행

while (!queue.isEmpty()){
  • 큐가 비어 있지 않은 동안 반복
  • 큐가 비었다는 것은 탐색할 노드가 없다는 의미, 탐색 완료

int[] pos = queue.poll();
int cx = pos[0], cy = pos[1];
  • queue.poll()를 통해 큐의 맨 앞에 있는 좌표 꺼내기
  • cs, cy : 현재 방문 중인 좌표
  • BFS는 큐에서 하나씩 꺼내면서 탐색 진행

for (int i = 0; i < 4; i++){
    int nx = cx + dx[i];
    int ny = cy + dy[i];
  • dx[], dy[] 배열을 사용하여 네 방향(상하좌우)으로 이동할 좌표(nx, ny)를 계산

if(nx >= 0 && ny >= 0 && nx < M && ny < N){
  • 이동할 좌표(nx, ny)가 배열 범위를 벗어나는지 확인

if(field[ny][nx] == 1 && !visited[ny][nx]){
  • 배추가 있는 곳(1)만 이동
  • 이미 방문한 곳visited[ny][nx] == true이라면 이동하지 않음

queue.offer(new int[]{nx, ny});
visited[ny][nx] = true;
  • 방문할 수 있는 좌표라면 queue.offer()을 사용하여 큐에 추가
  • 큐에 추가된 위치는 visited[][] = true로 설정해 중복 방문 방지

2. 코드 흐름 예시

M = 5, N = 5
배추 위치:
(1,1) (1,2) (2,2) (3,3) (4,3)

배추밭 배열(field[][])

0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
0 0 0 1 1
0 0 1 1 1

BFS 실행 흐름

  1. (0, 2)에서 탐색 시작 → BFS(0,2) 호출

    • 방문 처리 → visited[0][2] = true
    • 아래 (1, 2), 왼쪽 (1, 1), 오른쪽 (1, 3)을 큐에 추가
    • 큐 상태: [(1, 2), (1, 1), (1, 3)]

  2. (1, 2)에서

    • 방문 처리 → visited[1][2] = true
    • 아래 (2, 2)를 큐에 추가
    • 큐 상태: [(1, 1), (1, 3), (2, 2)]

  3. (1, 1)에서

    • 방문 처리 → visited[1][1] = true
    • 이동할 곳 없음
    • 큐 상태: [(1, 3), (2, 2)]

  4. (1, 3)에서

    • 방문 처리 → visited[1][3] = true
    • 이동할 곳 없음
    • 큐 상태: [(2, 2)]

  5. (2, 2)에서

    • 방문 처리 → visited[2][2] = true
    • 이동할 곳 없음
    • 첫 번째 군집 탐색 완료

  6. 새로운 배추 (3, 3)에서 BFS(3, 3) 호출

    • (3, 4), (4, 3), (4, 4)를 큐에 추가
    • 두 번째 군집 탐색 완료

2. 프로그래머스 문제 출이 및 코드 수정

1. 두 수의 나눗셈 문제 (형 변환 오류 수정)

  1. 작성 코드
class Solution {
    public int solution(int num1, int num2) {
        int answer = (num1/(double)num2) * 1000;
        return answer;
    }
}
  • 문제: 타입 캐스팅에 문제로 컴파일 에러
    num1 / (double) num2는 double 이지만 int 타입의 answer에 저장 하려고 함으로 타입 불일치 오류
  1. 수정 코드
class Solution {
    public int solution(int num1, int num2) {
        int answer = (int)((num1/(double)num2) * 1000);
        return answer;
    }
}
  • 해결: double을 바로 int에 저장 할 수 없음으로 형변환 및 정수 변환 진행

2. 짝수의 합 (변수 초기화 오류 수정)

  1. 작성 코드
class Solution {
    public int solution(int n) {
        int answer;
        for(int i = 0; i <= n; i++){
            if(i % 2 == 0){
                answer += i;
            }
        }
        return answer;
    }
}
  • 문제: answer 변수가 초기화 되지 않아 오류
    Java에서는 지역 변수를 초기화 하지 않으면 컴파일 오류 발생
  1. 수정 코드
class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i = 0; i <= n; i++){
            if(i % 2 == 0){
                answer += i;
            }
        }
        return answer;
    }
}
  • 해결: 변수 answer를 초기화하여 NullPointerException 방지

3. 배열 평균값 구하기(향상된 for문 적용)

  1. 일반 for문 사용
class Solution {
    public double solution(int[] numbers) {
        double answer = 0;
        int val = numbers.length;
        
        for(int i = 0; i < val; i++){
            int a = numbers[i];
            answer += a;
        }
        return answer/val;
    }
}
  1. 향상된 for문 적용
class Solution {
    public double solution(int[] numbers) {
        double answer = 0;
        int val = numbers.length;
        
        for(int num:numbers){
            answer += num;
        }
        return answer/val;
    }
}
profile
기 원
노력하고 있다니까요?
이전 포스트

[TIL]2025.02.28

다음 포스트

[JAVA]Queue

0개의 댓글