[프로그래머스] DFS/BFS - 네트워크(파이썬 문제 풀이)

문제 링크

코딩테스트 연습 - 네트워크

 

무방향 그래프가 computers로 주어집니다.

처음에는 그래프에서 1로 상하좌우가 묶여있는 덩어리들의 수를 세면 될 것이라고 생각했습니다. 그 결과.. 15점이 나왔습니다.

def DFS(x, y, n, computers):
    computers[x][y] = 0

    for k in range(4):
        xx = x + dx[k]
        yy = y + dy[k]
        if 0 <= xx < n and 0 <= yy < n and computers[xx][yy]:
            DFS(xx, yy, n, computers)

def solution(n, computers):
    global dx, dy

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

    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                DFS(i, j, n, computers)
                cnt += 1

예제 문제는 성공했지만 어째서인지 다른 테스트 케이스를 통과하지 못했습니다.

 

그러던 중 이런 반례를 찾았습니다.

n = 5

1 1 1 0 0
1 1 0 0 0
1 0 1 0 0
0 0 0 1 1
0 0 0 1 1

위와 같은 경우 네트워크의 수는 2인데 단순히 상하좌우로 묶여있는 덩어리의 수는 3개 입니다.

문제에 제시된 조건대로 연결되어있는 노드를 DFS로 탐색하여 방문한 곳은 0으로 바꾸는 과정을 computers의 모든 원소에 적용하니 해결되었습니다!

 

문제 풀이(파이썬)

---

def DFS(x, y, n, computers):
    computers[x][y] = 0

    for k in range(n):
        if computers[x][k] == 1:
            computers[x][k] = 0
            DFS(k, x, n, computers)

def solution(n, computers):
    global dx, dy

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

    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                DFS(i, j, n, computers)
                cnt += 1

    return cnt