[Python] Code up 4060: 전광판 전구 조작

https://codeup.kr/problem.php?id=4060

전광판 전구 조작

문제 설명

전광판에는 켜져 있는 전구(1)와 꺼져 있는 전구(0)가 있습니다. 전구를 조작하면 해당 전구와 상하좌우로 연결된 같은 상태의 전구들이 모두 바뀌는 특징이 있습니다. 이러한 규칙을 따라 모든 전구를 켜는 최소 조작 횟수와 끄는 최소 조작 횟수를 구하는 문제입니다.

입력

• 첫째 줄: 전광판의 크기 M N (2 ≤ M, N ≤ 100)
• 둘째 줄부터 M개의 줄에 걸쳐 N개의 전구 상태가 주어짐 (켜진 상태: 1, 꺼진 상태: 0)

출력

• 모든 전구를 켜기 위한 최소 조작 횟수와 모두 끄기 위한 최소 조작 횟수를 공백으로 구분하여 출력

 

해결 접근법

이 문제는 DFS(깊이 우선 탐색)을 활용하여 해결할 수 있었습니다.

1. 연결된 그룹 찾기
   • 같은 상태(0 또는 1)로 연결된 전구 그룹을 찾습니다.
   • DFS 를 사용하여 전구 그룹을 탐색합니다.
   • 한 그룹을 한 번의 조작으로 변환할 수 있으므로 그룹의 개수가 최소 조작 횟수가 됩니다.
2. 모든 전구를 켜기 위한 최소 조작 횟수
   • 0으로 이루어진 연결 요소(그룹)의 개수를 셉니다.
3. 모든 전구를 끄기 위한 최소 조작 횟수
   • 1으로 이루어진 연결 요소(그룹)의 개수를 셉니다.

소스 코드

def dfs(y,x):
    if y < 0 or y >= m or x < 0 or x>=n:
        return
    if grid[y][x]== "0":
        return   
    grid[y][x] = "0" #방문한 1을 0으로 변경하여 중복 방문 방지
    for d in range(4): # 상하좌우 탐색 
        dfs(y+dy[d],x+dx[d])

def dfs1(y,x):
    if y < 0 or y >= m or x < 0 or x>=n:
        return
    if grid2[y][x]== "1":
        return
    grid2[y][x] = "1" # 방문한 0을 1로 변경하여 중복 방문 방지
    for d in range(4):
        dfs1(y+dy[d],x+dx[d])


m,n = map(int, input().split()) 
grid = []
grid2 = []
for i in range(m):
    row = list(input().split())
    grid.append(row)
    grid2.append(row.copy()) #grid2는 grid의 복사본 (독립적 사용)
    #print(' '.join(map[i]))

dy = [1, -1, 0, 0] #상, 하, 좌, 우 4방향
dx = [0, 0, 1, -1]

cnt = 0 
cnt2 = 0
for i in range(m):
    for j in range(n):
        if grid[i][j] == "1": #1인 경우 DFS 실행 (꺼지는 그룹 찾기)
            dfs(i,j)
            cnt += 1
for i in range(m):
    for j in range(n):
        if grid2[i][j] == "0": #0인 경우 DFS 실행(켜지는 그룹 찾기)
            dfs1(i,j)
            cnt2 += 1
            
print(f'%d %d'%(cnt2,cnt))

 

저번에 소개한 DFS 기반 알고리즘과 비슷한 개념이지만, 이번 문제는 두 가지 개수를 찾아 출력해야 한다는 점에서 차이가 있습니다. 이를 독립적으로 해결하기 위해 두 개의 DFS 함수를 만들어 각각의 경우를 탐색하도록 구현했습니다. 다만, BFS를 활용하면 탐색을 더욱 효율적으로 진행할 수 있어 해결이 더 쉬워질 것 같습니다

 

마무리

1. DFS로 그룹을 찾고 조작 횟수를 계산하는 개념을 익힐 수 있는 좋은 문제!
2. BFS 공부를 통해 좀 더 개선된 코드 짜보기