BFS 알고리즘 | 백준#11123 #실버 | "양 한 마리, 양 두 마리" | 파이썬 풀이

📚 문제

문제 원본: https://www.acmicpc.net/problem/11123

11123번: 양 한마리... 양 두마리...

👨‍💻 접근법

⚙️사용 알고리즘: BFS

 

맵(i.e., 그래프)에 위치한

모든 양 각각을 기준으로 해당 양과 인접해 있는 다른 양의 존재여부를 확인하는 접근법을 활용했습니다.

🔥💻 소스코드 및 풀이과정

from collections import deque

# 테스트 케이스 개수 입력받기 
test_num = int(input())

# 탐색 방향별 이동할 좌표값
d = [(1, 0), (-1, 0), (0, -1), (0, 1)]

def bfs(x, y):
    # 새롭게 발견한 양의 위치를 저장할 큐 생성
    q = deque()
    q.append((x, y))
    # 발견한 양의 중복 탐지 방지
    graph[x][y] = '.'
    # 양들의 무리 수 확인이 끝날 때까지 반복 수행
    while q:
        x, y = q.popleft()
        # 상, 하, 좌, 우 인접한 양 찾기
        for dy, dx in d:
            nx, ny = y + dy, x + dx
            # 그래프 범위 내 미탐색 양 발견 시
            if (0 <= nx < h) and (0 <= ny < w) and graph[nx][ny] == '#':
                # 새롭게 발견한 양은 큐에 삽입
                q.append((nx, ny))
                # 발견한 양의 중복 탐지 방지
                graph[nx][ny] = '.'

# 테스트 케이스마다 결괏값(양 무리 수) 출력
for _ in range(test_num):
    # 양들의 위치 정보 입력받기
    h, w = map(int, input().split())
    graph = [list(input()) for _ in range(h)]
    # 결괏값: 양 무리 수 
    answer = 0
    for i in range(h):
        for j in range(w):
            # 양이 발견된 지점부터 탐색 시작
            if graph[i][j] == '#':
                bfs(i, j)
                answer += 1
    print(answer)

1)  양, 울타리 위치 표현

양과 울타리의 위치를 2차원 공간을 활용해 표현하였습니다.

예를 들어, 입력 예시에서 가장 좌측 상단의 위치 정보는 (0, 0)으로 표현할 수 있습니다.

파이썬 관점에서, 이를 이중 리스트 자료구조를 활용하였습니다.

예를 들어, 32째 줄에 graph 이름의 이중 리스트 [0][0] 인덱스에는

양 또는 울타리의 존재여부를 나타내는 값을 할당합니다.

2)  새로운 양 위치 탐지 수행

35~40째 줄과 같이, 

이중 리스트의 인덱스를 이중 for문으로 변경해 가며 해당 인덱스의 값이 양인지, 울타리인지 확인합니다.

양을 발견했다면 해당 양 주위에 또 다른 양이 있는지, 즉 무리를 이루고 있는지 여부를 확인해야겠죠?

이를 위해 함수를 따로 만들어 구현했으며, 해당 함수에는 발견한 양의 위치정보를 전달합니다.

3)  새로운 양 위치정보 저장용 큐 생성

발견한 임의의 양 주변에도 다른 양이 있는지 확인함으로써 양(들)을 하나의 무리에 편성할 수 있습니다.

즉, 처음 새롭게 발견한 양의 위치정보를 추가적인 탐색의 기준점으로서 따로 저장할 필요가 있습니다.

이를 위해 저는 큐(queue) 자료구조를 사용했습니다.

큐 자료구조를 사용한 이유는 선입선출 구조를 가지는 자료구조 특성을 활용하기 위함입니다.

즉, 먼저 찾은 양부터 먼저 무리를 편성하기 위함이죠. 큐 자료구조에 대한 자세한 내용은 이곳을 참고해 주세요 :)

9~11째 줄, bfs 함수 내 큐 자료구조를 생성합니다.

4)  탐지한 양 위치정보 저장 및 중복 탐지 방지

탐지한 양의 위치정보를 큐에 삽입합니다.

그리고 한 번 탐지한 양은 반드시 한 무리에만 편성됩니다. 여러 무리에 편성될 수 없는 것이죠.

따라서 같은 양을 2번 이상 탐지하는 것을 방지해야 합니다.

이를 14째 줄처럼 편의상 해당 위치에 울타리가 있다고 치환할 수 있습니다.

5)  무리 편성이 끝나지 않은 양의 존재여부 판단

탐지한 양들의 무리 편성이 끝났는지는 큐에 데이터가 존재하는지 여부로 확인할 수 있습니다.

따라서 큐에 데이터가 전혀 없을 때까지 임의의 양 인근에 다른 양이 있는지 확인하는 작업을 반복합니다(16째 줄).

6)  임의의 양 인근 새로운 양 탐지

탐지할 새로운 좌표는 기존 좌표에서 특정 탐지 방향에 맞는 값을 더하여 구현할 수 있습니다.

일곱째 줄에 상하좌우 순서대로 x, 축의 변화량을 미리 설정하였습니다.

19째 줄~20째 줄처럼 상하좌우 방향으로 이동한 새로운 좌표를 만들 수 있습니다.

7)  양 탐지 여부에 따른 2가지 절차

22째 줄과 같이, 문제에서 허용 가능한 범위 내에 새로운 양이 존재하는지 여부에 따라 절차가 2가지로 나뉩니다.

각각 살펴보겠습니다.

 

7-A)  새로운 양 탐지 시

먼저, 새로운 양이 존재한다면 다기 4) 절차부터 같은 순서로 수행합니다.

7-B)  (상하좌우 인근 내) 새로운 양 미탐지 시

만일 상하좌우 내 새로운 양을 발견하지 못 했다면 5) 절차부터 같은 순서로 수행합니다.

8)  무리 1개 증가 및 bfs 반복 수행

처음에 발견한 양 인근에는 더 이상 새롭게 탐지할 양이 존재하지 않는 경우입니다.

해당 양(들)을 하나의 무리로 편성했으므로 전체 무리 수를 1개 증가합니다.

초기에 양과 울타리의 위치정보를 설정한 이중 리스트의 모든 인덱스를 탐색할 때까지 bfs를 수행합니다.

9)  양 무리 수 출력

모든 인덱스를 탐색했다면 이제 해당 테스트 케이스의 양 무리 수를 출력합니다.

💡 느낀 점

✅ 전형적인 무리짓기 문제

본 문제는 전형적인 '무리짓기 문제 유형'입니다.

즉석으로 문제를 바꿔보자면 "얼음틀에 음료수를 부어 만들 수 있는 아이스크림 개수"로도 바꿀 수 있습니다.

BFS 알고리즘의 기본을 익힐 수 있는 훌륭한 예제라고 생각합니다.

이와 같은 유형의 문제에서는 탐색 이력(i.e., 노드 방문 이력)이 있는 노드는 중복 탐색을 방지하기 위해,

따로 방문 이력을 관리하는 기법이 가장 중요하다고 생각합니다.

참고할 만한 포스팅

이론 자료
1.  [알고리즘] 너비 우선 탐색(BFS) 알고리즘에 대해 알아보자!(+Python 구현)
2.  [알고리즘] 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자!(+Python 구현)
3.  [파이썬] map 함수에 대해 알아보자(Feat. lambda 표현식)
4.  [자료구조] 큐(Queue)에 대해 알아보자(+ Python)

관련 문제
1.  BFS 알고리즘 | 백준#11123 #실버 | "양 한 마리, 양 두 마리" | 파이썬 풀이
2.  BFS 알고리즘 | 백준#17086 #실버 | "아기상어2" | 파이썬 풀이
3.  DFS 알고리즘 #프로그래머스 #타겟넘버 | 파이썬 풀이
4.  BFS알고리즘 #프로그래머스 #가장 먼 노드 | 파이썬 풀이

---

피스백이나 질문 환영합니다!🔥

아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.

그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다.

고맙습니다 :)