[23-24 동계 모각코] 5회차 결과

모각코

[23-24 동계 모각코] 5회차 결과

모각모각 2024. 2. 2. 18:34

백준 10026 - 적록색약

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

문제링크 - https://www.acmicpc.net/problem/10026

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

문제 해결을 위해 고려한 조건 + 구현 방식

1. 일반인, 적록색약인 구분 방식

- 이 문제는 일반인과 적록색약인에게 보이는 색깔이 다르기 때문에, 각각에게 보이는 영역의 개수가 다르다. 따라서, 그리드를 구분하여 만들어줘야한다. (다른 방식을 이용할 수도 있지만 가장 효율적이라고 판단)

RRR
GGG
RRR

- 해당 영역을 일반인은 1번째 R영역, 2번째 G영역, 3번째 R영역으로 구분하지만 적록색약인은 R, G의 색상을 같다고 느끼기 때문에 1가지 영역으로만 생각한다.

n = int(sys.stdin.readline().strip())  # 그리드의 크기
grid = [list(map(str, sys.stdin.readline().strip())) for _ in range(n)]  # 그리드
weakness_grid = copy.deepcopy(grid)  # 적록색약 그리드

for i in range(n):
    for j in range(n):
        # 적록색약인 경우, 빨간색을 초록색으로 변경
        if weakness_grid[i][j] == "R":
            weakness_grid[i][j] = "G"

2. BFS 탐색 범위 및 방문처리

- 그리드의 범위인 NxN을 넘지 않도록, 0~n 범위 안에서만 탐색을 수행하도록 구현해야한다.

- 1. 시작 점을 먼저 방문처리 한다.

- 2. 그리드 범위 안에 있고, 방문하지 않은 위치 이며, 시작점의 색깔과 같은 색깔인 경우 방문 처리를 한다.

- ~~위 방식으로 하지 않고,~~ ~~큐(Queue)에서 popleft() 이후 바로 방문처리를 했을 때, 메모리 초과 또는 시간 초과가 발생한다.~~

queue = deque([(s[0], s[1])])  # 시작점을 큐에 추가
color = grid[s[0]][s[1]]  # 시작점의 색깔
visited[s[0]][s[1]] = True  # 시작점 방문 처리

while queue:
    x, y = queue.popleft()  # 큐에서 하나의 원소를 꺼내기
    # 상하좌우 탐색
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        # 범위 안에 있고, 방문하지 않았으며, 같은 색깔인 경우
        if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
            if grid[nx][ny] == color:
                visited[nx][ny] = True  # 방문 처리
                queue.append((nx, ny))  # 큐에 추가

3. BFS 탐색을 통한 영역 개수 세기

- 방문 여부를 저장하는 그리드와 같은 크기의 2차원 리스트를 생성해야 한다.

- 구역의 개수를 저장하는 변수를 생성하고, 방문하지 않은 구역을 BFS 탐색 이 후 일반인과 적록색약인이 보는 그리드의 색깔 영역의 개수를 셀 수 있다.

def count(n, grid):
    visited = [[False] * n for _ in range(n)]  # 방문 여부를 저장하는 2차원 리스트
    cnt = 0  # 구역의 개수

    for i in range(n):
        for j in range(n):
            # 방문하지 않은 경우
            if not visited[i][j]:
                bfs(n, grid, visited, (i, j))  # BFS 탐색
                cnt += 1  # 구역의 개수 증가

    return cnt

문제 리뷰

2번째 회차에서와 같이 BFS (너비 우선 탐색) 알고리즘을 이용하면 해결 할 수 있는 문제라고 파악했다. 일반인과 적록색약인 사람을 구분해서 탐색해야 한다는 사실을 고려해서 그리드에 보이는 영역의 개수를 세는 것이 핵심이다. BFS를 이용했을 때, 메모리 초과, 시간 초과가 발생하는 경우가 있었는데 방문 처리를 어떻게 하느냐에 따라 달라지는 것 같았다. 알고리즘을 따라 가보며 무엇이 문제인지 파악 해보려 했지만, 정확한 원인이 무엇인지는 잘 모르겠다. (영역 개수를 셀 때, 중복 방문이 되는 것이라고 의심)

너비 우선 탐색 (BFS)

BFS(너비 우선 탐색)는 그래프나 트리의 노드를 탐색하는 알고리즘 중 하나로, 시작 노드로부터 가까운 노드부터 순서대로 탐색해 나가는 방식이다. 또한, 그래프 탐색, 최단 경로 찾기, 네트워크 트러버스 등 다양한 분야에서 활용되며, 특히 최단 경로 문제에 강점을 가지고 있다. 해당 문제를 해결하기 위해서 BFS는 큐(Queue)를 사용하여 구현하였고, 영역의 개수를 세기 위한 count함수를 따로 구성하여, BFS의 방문여부를 확인해서 카운트하는 방식으로 구현했다.

일반적으로 BFS는 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. 예를 들어, 지구상의 존재하는 모든 인관관계를 표현한 후 철수와 영희 사이에 존재하는 경로를 찾는 경우를 생각해 볼 수 있다.

장점

- 출발 노드에서 목표노드까지의 최단 거리를 보장한다.

단점

- 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 메모리가 소요된다.

- 원하는 해가 존재 하지 않는 유한 그래프의 경우, 그래프의 모든 노드를 탐색해도 결과를 낼 수 없다.

- 원하는 해가 존재 하지 않는 무한 그래프의 경우, 무한히 그래프를 탐색하여 예외처리 없이 결과를 낼 수 없다.

주요 특징

큐(Queue) 활용

- BFS는 큐를 사용하여 탐색할 노드들을 저장하고, 노드를 방문한 순서대로 처리한다. 새로 발견된 노드는 큐에 추가하고, 큐의 맨 앞에서부터 노드를 꺼내어 처리한다.

레벨 단위 탐색

- BFS는 시작 노드로부터 거리가 가까운 순서대로 탐색하기 때문에 레벨 단위로 탐색이 이루어진다. 즉, 시작 노드로부터 거리가 1인 노드를 모두 방문한 후에, 거리가 2인 노드들을 방문하게 된다.

최단 경로 찾기

- BFS는 가장 먼저 도착한 노드가 목표 노드에 대한 최단 경로를 제공한다. 이는 레벨 단위로 탐색하기 때문에 해당 레벨에서 목표 노드에 도달하는 경우, 그 이전 레벨에서 이미 더 가까운 경로가 없음을 의미한다.

방문한 노드 표시

- 각 노드를 방문할 때 해당 노드를 방문했음을 표시하여 중복 방문을 방지한다. 이는 그래프의 순환을 탐지하거나 무한 루프를 방지하는 데에 도움이 된다.

시간 복잡도

- BFS의 시간 복잡도는 O(V + E)이다. 여기서 V는 노드의 수, E는 간선의 수이다

코드 설명

def bfs(n, grid, visited, s):
    # 상, 하, 좌, 우
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    queue = deque([(s[0], s[1])])  # 시작점을 큐에 추가
    color = grid[s[0]][s[1]]  # 시작점의 색깔
    visited[s[0]][s[1]] = True  # 시작점 방문 처리

    while queue:
        x, y = queue.popleft()  # 큐에서 하나의 원소를 꺼내기
        # 상하좌우 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            # 범위 안에 있고, 방문하지 않았으며, 같은 색깔인 경우
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if grid[nx][ny] == color:
                    visited[nx][ny] = True  # 방문 처리
                    queue.append((nx, ny))  # 큐에 추가

해당 문제를 해결하기 위한 BFS 탐색 함수이다. 이 함수는 그리드의 크기 n, 그리드, 방문여부 리스트, 시작점을 입력으로 받아 큐(Queue)를 이용하여 BFS 탐색을 수행한다.

먼저 큐(Queue)에 시작점을 추가하고, 시작점의 색깔을 color에 저장한다. 또한 시작점을 방문처리 해준다.

이 후 반복문을 통해 그리드의 4방향 범위를 탐색하고, 조건에 맞는 경우 방문처리 한다.

def count(n, grid):
    visited = [[False] * n for _ in range(n)]  # 방문 여부를 저장하는 2차원 리스트
    cnt = 0  # 구역의 개수

    for i in range(n):
        for j in range(n):
            # 방문하지 않은 경우
            if not visited[i][j]:
                bfs(n, grid, visited, (i, j))  # BFS 탐색
                cnt += 1  # 구역의 개수 증가

    return cnt

영역의 개수를 세기 위한 count 함수이다. 이 함수는 그리드의 크기 n과 그리드를 입력받아 방문여부를 저장하는 2차원 리스트를 생성하고 BFS탐색 함수를 통해 영역의 개수를 센다.

def main():
    n = int(sys.stdin.readline().strip())  # 그리드의 크기
    grid = [list(map(str, sys.stdin.readline().strip()))
            for _ in range(n)]  # 그리드
    weakness_grid = copy.deepcopy(grid)  # 적록색약 그리드

    for i in range(n):
        for j in range(n):
            # 적록색약인 경우, 빨간색을 초록색으로 변경
            if weakness_grid[i][j] == "R":
                weakness_grid[i][j] = "G"

일반인과 적록색약인의 그리드를 구분하기위해, 적록색약인의 그리드에서 R(빨간색)을 G(초록색)으로 변경한다.

전체 코드

from collections import deque
import sys
import copy


def bfs(n, grid, visited, s):
    # 상, 하, 좌, 우
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    queue = deque([(s[0], s[1])])  # 시작점을 큐에 추가
    color = grid[s[0]][s[1]]  # 시작점의 색깔
    visited[s[0]][s[1]] = True  # 시작점 방문 처리

    while queue:
        x, y = queue.popleft()  # 큐에서 하나의 원소를 꺼내기
        # 상하좌우 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            # 범위 안에 있고, 방문하지 않았으며, 같은 색깔인 경우
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if grid[nx][ny] == color:
                    visited[nx][ny] = True  # 방문 처리
                    queue.append((nx, ny))  # 큐에 추가


def count(n, grid):
    visited = [[False] * n for _ in range(n)]  # 방문 여부를 저장하는 2차원 리스트
    cnt = 0  # 구역의 개수

    for i in range(n):
        for j in range(n):
            # 방문하지 않은 경우
            if not visited[i][j]:
                bfs(n, grid, visited, (i, j))  # BFS 탐색
                cnt += 1  # 구역의 개수 증가

    return cnt


def main():
    n = int(sys.stdin.readline().strip())  # 그리드의 크기
    grid = [list(map(str, sys.stdin.readline().strip()))
            for _ in range(n)]  # 그리드
    weakness_grid = copy.deepcopy(grid)  # 적록색약 그리드

    for i in range(n):
        for j in range(n):
            # 적록색약인 경우, 빨간색을 초록색으로 변경
            if weakness_grid[i][j] == "R":
                weakness_grid[i][j] = "G"

    print(count(n, grid), count(n, weakness_grid))


if __name__ == "__main__":
    main()

# BFS(너비 우선 탐색) 알고리즘을 활용하여 풀 수 있는 문제라고 생각했고, 2회차 때 BFS 관련 문제보다 쉽고 빠르게 문제를 해결 할 수 있어서 한 단계 성장했다는 느낌을 받았다. 일반인과 적록색약인의 그리드 구분을 단순하게 빨간색을 초록색으로 바꾸는 방식으로 코드를 구현했기 때문에, 더 간결하게 또 다른 방식으로 구현할 수 있을지 고민해봐야겠다.