[BOJ] 2668 단지번호붙이기 - dfs, graph

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

이번 프로그래머스 winter coding 3번 문제와 매우 흡사한 문제이다. 

union find를 해야 풀리는 문제인지 알았는데, 그래프가 아닌 이차원 배열 같은 경우 이를 구현하기가 상당히 까다롭다.

그리고 이런 구역 나누기 문제는 간단한 dfs로 해결 가능하다. 맵의 처음부터 끝까지 차례대로 순회하여 같은 구역일 경우 dfs를 계속 진행하고, 다른 구역인 경우 그 구역의 value로 또 dfs를 진행하며 visited를 체크한다.

쉽게 dfs로 구현 가능하니 생각해두자.

밑의 코드는 프로그래머스 winter coding 3번 문제 풀이

x_dir = [-1, 1, 0, 0]
y_dir = [0, 0, -1, 1]
 
 
 
def solution(v):
 
    def dfs(x, y, value):
 
        visited[x][y] = True
        for i in range(4):
            nx = x+x_dir[i]
            ny = y+y_dir[i]
 
            if nx < 0 or nx >= length or ny < 0 or ny >= length:
                continue
 
            if visited[nx][ny]:
                continue
 
            if v[nx][ny] != value:
                continue
            else:
                dfs(nx, ny, value)
 
    answer = []
 
    fruit = [0] * 4
 
    length = len(v)
    visited = [[False for _ in range(length)] for _ in range(length)]
 
    now = 4
 
    for i in range(length):
        for j in range(length):
            if v[i][j] != now and not visited[i][j]:
                visited[i][j] = True
                now = v[i][j]
                dfs(i, j, now)
                fruit[v[i][j]] += 1
 
    print(fruit)
    return answer
 
 
v= [[0,0,1,1],[1,1,1,1],[2,2,2,1],[0,0,0,2]]
solution(v)