[백준 16946번] 벽 부수고 이동하기 4 - 파이썬

문제 링크:

https://www.acmicpc.net/problem/16946

16946번: 벽 부수고 이동하기 4

 

---

풀이 유형:

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 플러드 필(Flood fill)

 

★문제풀이 Point★

1. 0으로 인접해 있는 위치들을 같은 그룹으로 묶어준다. (플러드 필 = 색칠 알고리즘 이용)

2. 각 그룹별로 0의 개수가 몇 개인지 딕셔너리에 저장한다. 

3. 벽으로 된 위치를 상하좌우를 돌며 인접한 그룹들을 구한 뒤, 그룹에 해당하는 0의 개수를 모두 더해준다.

 

풀이 과정:

 

이 문제는 백준 난이도 골드 2로써, 2022.3.1일 기준 내가 풀었던 문제 중에 가장 어려운 문제에 속한다. 

처음 문제 접근은 벽을 만나게 되면(1), 그 벽을 아무것도 없는 곳으로 바꾼 후( 1 -> 0), 너비 우선 탐색을 실시하여 0의 개수를 구하려고 했다. 하지만 이 문제는 N, M 최대가 1000이고 시간제한이 2초밖에 주어지지 않았다. 따라서 시간 초과가 날 것이 분명했다. 따라서 다른 접근 방법이 필요하여 구글링을 통해 플러드 필 알고리즘을 알게 되었다.

플러드 필 알고리즘:

플러드 필 알고리즘

플러드 필 알고리즘(Flood Fill)이란 다음 그림처럼 배열에 있는 시작 칸에서 목표 색으로 연결된 모든 칸을 방문해서 대체 색으로 바꾸는 알고리즘이다.

이 문제에서는 0으로 인접해 있는 모든 개수를 세주는 것이 플러드 필 알고리즘에 해당한다.

이제 문제를 풀어보자.

1. 0으로 인접한 칸들을 모두 그룹으로 묶고 번호를 매겨준다. (플러드 필)

      0으로 인접한 칸들을 그룹으로 묶기                =>         벽인 칸은 0으로 모두 바꾸고 0으로 인접한 칸들을 1부터 순서대로 그룹 번호 매기기

 

2. 위를 토대로 각 그룹별로 개수가 몇 개인지 세어 딕셔너리에 저장한다.

1번 그룹: 2개, 2번 그룹: 3개, 3번 그룹: 1개, 4번 그룹: 1개, 5번 그룹: 1개, 6번 그룹: 1개 이므로...

예시로 info = {1: 2, 2: 3, 3: 1, 4: 1, 5: 1, 6: 1} 이렇게 만들 수 있다.

 

3. 벽으로 된 위치를 상하좌우를 돌며 인접한 그룹들을 구한 뒤, 그룹에 해당하는 0의 개수를 모두 더해준다.

 

예를 들어, (2, 1) 위치에 파란색으로 표시되어 있는 벽을 살펴보자. 현 위치에서 상하좌우를 확인한 다음, 연두색으로 칠해져 있는 그룹들의 개수를 모두 더해주면(2그룹:3개 + 3그룹: 1개 + 5그룹: 1개) 답( =5개)을 얻을 수 있다.

 

백준 16946번 채점 결과

 

이제 풀이 방식을 대략적으로 알았다면, 각자 코드를 작성해보자.

풀이 코드만 복사해서 답을 맞히는 거는 실력을 키우는데 전혀 도움이 안 된다.

 

풀이 코드:

• visited: 방문 표시를 확인하는 배열로서, 모든 값을 0으로 초기화하였다.
• zeros: 그룹번호를 알려주는 배열로서, info 딕셔너리와의 조합이 이루어진다.
• answer: 답을 출력할 때 사용하는 배열이다.
• data: 그룹 번호를 담기 위한 집합 데이터 생성(집합 데이터로 만드는 이유는 중복을 제거하기 위함)
• bfs(start_x, start_y): 현 위치에서 방문할 수 있는 개수를 세주는 함수
• move_count(x, y): 현 위치에서 이동할 수 있는 총그룹의 개수를 세주는 함수
• info: key값으로 그룹번호, values값으로 그룹의 개수를 표현해주는 딕셔너리
• group: 1부터 차례대로 그룹의 번호를 부여해주는 정수 자료형

 

# 16946번 벽 부수고 이동하기 4

from collections import deque

# 현 위치에서 방문할 수 있는 개수를 세는 함수
def bfs(start_x, start_y):
    q = deque()
    q.append((start_x, start_y))
    # 시작 위치 방문 표시
    visited[start_x][start_y] = 1
    # 시작 위치 개수 세기
    cnt = 1
    # 큐가 빌 때까지
    while q:
        x, y = q.popleft()
        # 현재 그룹에 포함
        zeros[x][y] = group
        # 4가지 이동 방향에 대하여
        for i in range(4):
            # 이동 위치 확인
            nx, ny = x + dx[i], y + dy[i]
            # 이동할 위치가 맵을 벗어나면 건너뛰기
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 이미 방문한 위치라면 건너뛰기
            if visited[nx][ny]:
                continue
            # 이동할 위치가 빈 곳이라면
            if not graph[nx][ny]:
                # 큐에 추가
                q.append((nx, ny))
                # 방문 표시
                visited[nx][ny] = 1
                # 개수 세기
                cnt += 1
    return cnt

# 이동할 수 있는 총 그룹의 개수를 세는 함수
def move_count(x, y):
    # 그룹 번호를 담기 위한 집합 데이터 생성
    data = set()
    # 4가지 방향에 대하여
    for i in range(4):
        # 이동 위치 확인
        nx, ny = x + dx[i], y + dy[i]
        # 맵을 벗어나면 건너뛰기
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        # 그룹에 속해 있지 않는 위치 건너뛰기
        if not zeros[nx][ny]:
            continue
        # 현재 그룹에 포함된 개수를 집합 데이터에 추가
        data.add(zeros[nx][ny])
    # 현재 x, y 위치 세기
    cnt = 1
    # 갈 수 있는 모든 그룹에 대하여 한 그룹씩 받으면서
    for c in data:
        # 딕셔너리에 추가
        cnt += info[c]
        # 이동할 수 있는 칸의 개수를 10으로 나눈 나머지 계산
        cnt %= 10
    # 출력값 반환
    return cnt

# 문제에서 주어진 데이터 입력받기
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]

# 방문 표시 확인 2차원 배열
visited = [[0] * m for _ in range(n)]
# 그룹 번호를 알려주는 2차원 배열
zeros = [[0] * m for _ in range(n)]
# 출력값을 나타내는 2차원 배열
answer = [[0] * m for _ in range(n)]

# 1번 그룹 생성
group = 1
# (그룹명, 그룹 안에 포함된 총 개수) 딕셔너리 생성
info = {}

# 상, 하, 좌, 우 위치 확인
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 전체 데이터를 하나씩 살펴보며
for i in range(n):
    for j in range(m):
        # 이동할 수 있거나 아직 방문하지 않은 위치라면
        if not graph[i][j] and not visited[i][j]:
            # 현재 위치에서 이동할 수 있는 0의 개수 세기
            cnt = bfs(i, j)
            # 딕셔너리에 그룹명과 개수 추가
            info[group] = cnt
            # 다음 그룹
            group += 1
# 전체 데이터를 하나씩 살펴보며
for i in range(n):
    for j in range(m):
        # 벽이 있다면
        if graph[i][j]:
            # 벽을 부수고 인접해 있는 그룹의 총 개수 받기
            answer[i][j] = move_count(i, j)
# 정답 출력
for i in range(n):
    print("".join(map(str, answer[i])))

 

 

16946 벽 부수고 이동하기 4