[Python] Code up 4024: 호수의 수 구하기

https://codeup.kr/problem.php?id=4024&rid=0

호수의 수 구하기

 

문제 설명 

CodeUp 4024번 문제는 'L' 과 '.' 으로 구성된 지도를 통해 호수의 개수를 구하는 문제입니다. 이때 'L'은 호수를 의미하고 '.'은 비호수 지역을 의미합니다. 호수는 상, 하, 좌, 우, 대각선으로 연결된 모든 'L' 을 하나의 호수로 간주합니다. 

해결 접근법

일단 이 문제를 마주했을 때, DFS 알고리즘을 활용해야겠다는 생각이 들었습니다.

DFS는 한 지점에서 시작해 갈 수 있는 모든 경로를 탐색하기 때문에 호수의 모든 연결 요소를 방문하는 데 적합하다고 생각했기 때문입니다.

 

소스코드

import sys
sys.setrecursionlimit(10**6) #기본 재귀 깊이 제한을 늘려주기 10의 6제곱으로 

def dfs(y,x): #dfs 함수 선언
    if y < 0 or y >= h or x < 0 or x >= w: #높이 와 너비보다 크거나 0 보다 작으면
        return
    if lake[y][x]==".": #.을 만나면
        return
    if lake[y][x]=="L": # L을 만나면
        lake[y][x]="." # L을 . 으로 바꿔주고
        for d in range(8): #8방향 상, 하 , 좌 , 우 , 대각선 
            dfs(y+dy[d], x+dx[d])
        
w,h = map(int, input().split())
lake = []
for i in range(h):
    row = list(input().split()) #한 줄에 입력 받으려면 list로 
    lake.append(row)#lake 에 append(추가) 해주기

dx = [1, 1, 1, 0, 0, -1, -1, -1] #x좌표
dy = [-1, 0, 1, 1, -1, 0, 1, -1] #y좌표


cnt = 0 #호수의 개수 변수
for i in range(h):# 모든 좌표를 순회하면서 DFS 실행 
    for j in range(w):
        if lake[i][j] == "L":
            dfs(i,j)
            cnt+=1
            
print(cnt)

 

제 코드는 순회하면서 돌다가 'L'을 발견하면 DFS 를 시작하고 연결된 모든 'L'을 방문 처리 합니다. 재귀함수로 만들어준 DFS 함수는 다음 미방문 'L'을 찾아 위 과정을 반복하게되고 ,  DFS 가 끝날때마다 호수의 개수를 증가시키게 해주었습니다.

또 다른 풀이법

# 입력 받기
W, H = map(int, input().split())
map_data = [input().split() for _ in range(H)]

# 방향 벡터 (상, 하, 좌, 우, 대각선)
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

# DFS 함수 정의
def dfs(x, y):
    # 현재 위치를 방문 처리
    map_data[x][y] = '.'
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and map_data[nx][ny] == 'L':
            dfs(nx, ny)

lake_count = 0

# 모든 좌표를 순회하며 DFS 실행
for i in range(H):
    for j in range(W):
        if map_data[i][j] == 'L':
            dfs(i, j)
            lake_count += 1

print(lake_count)

 

 

추가학습

1. BFS 개념 공부 및 관련 알고리즘 문제 풀이
2. 연결 요소 문제: 백준 4963 (섬의 개수), 2667(단지 번호 붙이기) 등의 문제 풀기