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

정기홍·2024년 12월 4일
BFSDFSpython코딩테스트
0

코딩테스트_파이썬

목록 보기
23/49

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

  • 벽을 부수고 이동할 수 있는 곳으로 변경한다.
  • 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

  • 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

  • 맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

풀이

import sys
from collections import deque


input = sys.stdin.readline

# 0의 갯수를 세고, 어디에 소속되어 있는지 기록하는 함수
def count_zero(x,y,cluster_num):
    global cluster
    q = deque()
    q.append((x,y))
    cluster[y][x] = cluster_num
    cnt = 1
    while q:
        a,b = q.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if(0<=nx<m and 0 <= ny <n):
                if cluster[ny][nx]==0 and grid[ny][nx] == 0:
                    cluster[ny][nx] = cluster_num
                    q.append((nx,ny))
                    cnt += 1
    return cnt

n,m = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(list(map(int,input().strip())))
# 각 클래스터 그룹 번호 = 인덱스 기준 , 0의 갯수 기록
cluster_record = [0]
# 클러스터 넘버링
cluster_num = 1
# 그리드로 클러스트 그룹별 번호 기록 
cluster =  [[0]*m for _ in range(n)]

# 상하좌우 설정
dx = [-1,1,0,0]
dy =  [0,0,-1,1]

# 0의 갯수를 세고, 어느 클러스터에 소속되어 있지 않다면 진행.
for x in range(m):
    for y in range(n):
        if grid[y][x] == 0 and cluster[y][x] == 0 :
            cnt_zero = count_zero(x,y,cluster_num)
            cluster_record.append(cnt_zero%10)
            cluster_num += 1


# 클러스터 그룹과 1을 부쉈을 때를 기준으로, grid를 새로 업데이트
for x in range(m):
    for y in range(n):
        if grid[y][x] == 1:
            cluster_grid = set()
            for a in range(4):
                nx = x + dx[a]
                ny = y + dy[a]
                if (0<=nx<m and 0 <= ny <n):
                    cluster_grid.add(cluster[ny][nx])
            for i in cluster_grid:
                grid[y][x]+= cluster_record[i]
            grid[y][x] %= 10

for y in grid:
    for x in y:
        print(x, end='')
    print()

오답 풀이

첫 번째 코드

import sys
from collections import deque
input= sys.stdin.readline

n, m = map(int, input().split())

grid =[]

for _ in range(n):
    a = list(map(int, input().strip()))  # 공백으로 구분된 정수 입력 받기
    grid.append(a)


# 상하좌우 설정
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def dfs(x,y):
    visited = [[False]*m for _ in range(n)]
    q = deque()
    q.append([x,y])
    visited[y][x]= True
    cnt = 1

    while q:
        a,b = q.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if (0<= nx < m and 0<= ny <n):
                if grid[ny][nx] == 0 and not visited[ny][nx]:
                    q.append((nx,ny))
                    visited[ny][nx] = True
                    cnt += 1
    return cnt%10


for y in range(n):
    for x in range(m):
        if grid[y][x]==1:
            grid[y][x] = dfs(x,y)
        

for y in grid:
    for x in y:
        print(x,end='')
    print()

그냥 간단하게 전부다 확인하면서 하면 될 줄 알았더니, 시간 복잡도가 O(n^3)이므로, 매우 안 좋다.
그렇기 때문에 시간 복잡도를 O(n^2)으로 줄일 필요가 있었고, 결국 아이디어를 하나 가져와서 풀게 되었다.
ㅎ...
보니까 매우 어렵다고 한다.

두 번째 코드

(사실 그전에 수많은 도전이 있었다... 시간 초과를 뚫기 위해...)

import sys
from collections import deque

input = sys.stdin.read
data = input().splitlines()

n, m = map(int, data[0].split())
grid = [list(map(int, line.strip())) for line in data[1:n+1]]

cluster_record = [0]
cluster_num = 1
cluster = [0] * (n * m)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def count_zero(x, y, cluster_num):
    visited = [False] * (n * m)
    q = deque()
    q.append((x, y))
    cluster[y * m + x] = cluster_num
    visited[y * m + x] = True
    cnt = 1

    while q:
        a, b = q.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if not visited[ny * m + nx] and grid[ny][nx] == 0:
                    visited[ny * m + nx] = True
                    cluster[ny * m + nx] = cluster_num
                    q.append((nx, ny))
                    cnt += 1
    return cnt

for x in range(m):
    for y in range(n):
        if grid[y][x] == 0 and cluster[y * m + x] == 0:
            cnt_zero = count_zero(x, y, cluster_num)
            cluster_record.append(cnt_zero % 10)
            cluster_num += 1

for x in range(m):
    for y in range(n):
        if grid[y][x] == 1:
            cluster_grid = set()
            for a in range(4):
                nx = x + dx[a]
                ny = y + dy[a]
                if 0 <= nx < m and 0 <= ny < n:
                    cluster_grid.add(cluster[ny * m + nx])
            for i in cluster_grid:
                grid[y][x] += cluster_record[i]
            grid[y][x] %= 10

for row in grid:
    print(''.join(map(str, row)))

결론적으로 여기서 가장 큰 문제점은 기록을 하는데에, 시간을 너무 많이 잡아먹는다는 점이었다. 그렇기 때문에, 기록을 하는 대신, 클러스터에 기록함으로써, 기록과 어느 클러스터에 속해있는지 동시에 기록했다.
코드를 분석하면 무슨 내용인지 이해가 갈거라고 생각한다. ...

후기

  • a = list(map(int, input().strip())) # 공백으로 구분된 정수 입력 받기

    • 붙어 있는 문자열의 경우, 다음과 같이 받아야 한다.

  • 진짜 너무너무 어려웠다. 진심.

profile
정기홍
하나를 알고 그걸로 모든걸 관통한다.
이전 포스트

Python의 `strip()` 메서드 다루기

다음 포스트

[백준] 2206번 벽 부수고 이동하기

0개의 댓글