요즘처럼 사회적 거리두기가 중요해진 시대에, 좌석 배치 최적화는 매우 중요한 문제입니다. 특히 극장이나 강의실과 같이 많은 사람들이 모이는 공간에서는 효율적인 좌석 배치를 통해 감염 위험을 최소화하고 공간 활용도를 높일 수 있습니다. 이 글에서는 좌석 배치 문제를 해결하는 데 유용한 두 가지 알고리즘인 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)에 대해 알아보고, 실제 코드 예시를 통해 그 차이점과 활용 방법을 설명하겠습니다. 문제 상황은 2차원 배열로 표현된 좌석 정보에서 서로 인접하지 않은 그룹의 수를 구하는 것입니다. 0은 빈 좌석, 1은 사람이 앉은 좌석을 의미합니다.
코드에서는 2차원 배열 seats에 좌석 정보가 담겨있다고 가정합니다. seats[i][j] == 1이면 해당 좌석에 사람이 앉아있고, seats[i][j] == 0이면 빈 좌석입니다. 우리는 BFS를 이용하여 서로 연결된 좌석 그룹(사람들이 앉아 있는 그룹)을 찾아 각 그룹의 개수를 세어 답을 구합니다. 먼저, 방문 여부를 확인하기 위한 visited 배열을 생성합니다. BFS는 큐 자료구조를 활용하여 탐색을 진행합니다. 처음 만나는 좌석이 사람이 앉아있는 좌석(seats[i][j] == 1)이라면, 그 좌석을 시작점으로 하여 상하좌우 인접한 좌석들을 탐색합니다. 인접한 좌석이 사람이 앉아있고 아직 방문하지 않았다면(visited[i][j] == 0 && seats[i][j] == 1) 큐에 추가하고 방문 표시(visited[i][j] = 1)를 합니다. 큐가 빌 때까지 이 과정을 반복하면 하나의 그룹 탐색이 완료됩니다. 하나의 그룹 탐색이 완료될 때마다 answer 변수의 값을 증가시킵니다. 이렇게 모든 좌석을 탐색하면 answer에는 서로 인접하지 않은 그룹의 수가 저장됩니다. DFS의 경우에도 동일한 논리를 사용하지만, 큐 대신 스택 자료구조를 사용하고 재귀 호출을 통해 깊이 우선적으로 탐색하는 차이가 있습니다. BFS는 너비 우선적으로 탐색하기 때문에 가까운 좌석부터 탐색하여 최단 경로 탐색 등에 유용하고, DFS는 깊이 우선적으로 탐색하여 특정 조건을 만족하는 경로를 찾는 데 유용합니다. 하지만 이 문제에서는 두 알고리즘 모두 같은 결과를 출력합니다.
결론적으로, DFS와 BFS 알고리즘은 좌석 배치 문제와 같이 그래프 탐색이 필요한 문제 해결에 효과적으로 사용될 수 있습니다. 문제의 특성에 따라 알고리즘을 선택하는 것이 중요하며, 이 글에서는 BFS를 이용하여 좌석 배치 문제를 해결하는 방법을 제시했습니다. 하지만 DFS를 이용하여도 동일한 결과를 얻을 수 있습니다. 본 예시는 간략화된 모델이며, 실제 좌석 배치 최적화 문제는 더욱 복잡한 조건과 제약 조건을 고려해야 함을 잊지 말아야 합니다.