[코딩테스트] Programmers - 네트워크 (실패)

 
https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 
 

풀이

 
문제 제한사항 

• 1 <= 컴퓨터 개수(n) <= 200
• 컴퓨터는 0 ~ (n-1)으로 표현
• i 컴퓨터와 j 컴퓨터가 연결되어 있다. -> computers[i, j] = 1로 표현 
• computers[i, j]은 1이다. -> 자기 자신과는 연결되어 있다. 

 
cf) 
computers = 연결 정보 2차원 배열
 
일단 문제 유형이 BFS, DFS이므로 BFS로 풀어보려 했다. 
 
첫 번째 예시를 보자. 
computers =
[
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1]
]
 
(i, j)부터 BFS탐색을 해보면, 더 이상 탐색할 수 없는 순간이 온다. 그때는 간접 연결된 경우가 없다는 것이므로 네트워크 개수를 1 늘려주면 된다. 
이 과정을 computers 배열을 다 탐색할 때까지 BFS 탐색을 해주면 된다. 
 
 

코드1 - 오답

using System;
using System.Collections.Generic;

public class Solution {
    
    public int BFS(int[,] computers)
    {
        Queue<(int x, int y)> queue = new Queue<(int x, int y)>();
        
        bool[,] visit = new bool[computers.GetLength(0), computers.GetLength(1)];
        int[] dx = { 0, 0, -1, 1 };
        int[] dy = { -1, 1, 0, 0 };
        
        int answer = 0; 
        
        for(int i = 0; i < computers.GetLength(0); i++)
        {
            for(int j = 0; j < computers.GetLength(1); j++)
            {
                // 연결되었으며 방문한 적 없으면 
                if(computers[i, j] == 1 && !visit[i, j] && !visit[j, i])
                {
                    visit[i, j] = true; // 방문 표시 
                    queue.Enqueue((i, j)); // 방문한 좌표 큐에 넣기. (상하좌우 탐색하기 위해)
                }
                // 연결되지 않았거나, 방문한 적 있으면 
                else
                    continue;
                
                // 연결되었으며 방문한 적 없으면 
                // 큐에 원소가 빌때까지 반복 
                while(queue.Count > 0)
                {
                    (int x, int y) basePos = queue.Dequeue();
                    
                    // 상하좌우 탐색
                    for(int dir = 0; dir < 4; dir++)
                    {
                        int posX = basePos.x + dx[dir];
                        int posY = basePos.y + dy[dir];
                        
                        // 인덱스 범위를 벗어나면 
                        if(posX < 0 || posX >= computers.GetLength(0) || 
                           posY < 0 || posY >= computers.GetLength(1))
                            continue;
                        
                        // 연결되지 않거나, 방문한 적 있는 곳이면
                        if(computers[posX, posY] == 0 || visit[posX, posY] || visit[posY, posX])
                            continue;
                        
                        // 인덱스 범위 벗어나지 않고, 연결되었고, 방문한 적 없으면 
                        visit[posX, posY] = true; // 방문 표시
                        queue.Enqueue((posX, posY)); // 해당 좌표를 큐에 넣기. (다음에 탐색하기 위함)
                    }

                    // 상하좌우 탐색했는데 다음 탐색할 좌표가 없으면 
                    // if(queue.Count <= 0)
                    //     answer--;
                }
                answer++;
            }
        }
        
        return answer;
    }
    
    public int solution(int n, int[,] computers) {
        
        return BFS(computers);
        
    }
}

예제와 테스트케이스 2, 테스트케이스 5는 통과했지만 다른 테스트케이스에서 실패가 나왔다. 
여러 테스트케이스를 생각해 보고 대입해 보니, computers가 [ [1, 0, 1], [0, 1, 0], [1, 0, 1] ]인 경우 정답은 2이다. 그러나 내 코드에서는 5가 나온다. 
 
 

풀이2 

한참 고민을 하다 다른 사람 코드를 보고 해봤지만, 눈에 잘 들어오지 않았다. 그래서 llm으로 내 코드가 왜 틀렸는지 파악후 코드를 참고해서(거의 그대로 가져왔다...) 문제를 풀어봤다. 
 
나는 격자 탐색에서 사용되는 BFS 코드를 사용했다. 
이 문제는 그래프 탐색이다. 그래프 탐색은 격자 탐색 BFS로 풀 수 없다. 
왜 그래프 탐색 문제는 격자 탐색 BFS로 풀 수 없을까? 
그래프는 정점과 간선으로 이루어진 것이다. (x, y)로 표현할 수가 없다. 그러니 그래프 탐색은 격자 탐색 BFS로 풀 수 없다. 
그러면 어떻게 그래프 탐색 문제를 풀어야 할까? 
2차원 배열이 아니라 1차원 배열로 문제를 풀면 된다. 
 
 

코드2 - 정답

using System;
using System.Collections.Generic;

public class Solution {
    
    public void BFS(int[,] computers, int n, int startComputer, bool[] visit)
    {
        Queue<int> queue = new Queue<int>(); // BFS 탐색에 사용할 큐

        // 일단 시작 컴퓨터 방문 처리부터 
        visit[startComputer] = true;
        queue.Enqueue(startComputer);

        while(queue.Count > 0)
        {
            int currentComputer = queue.Dequeue();

            for(int nextComputer = 0; nextComputer < n; nextComputer++)
            {
                if(currentComputer == nextComputer) continue;

                if(computers[currentComputer, nextComputer] == 1 && !visit[nextComputer])
                {
                    visit[nextComputer] = true;
                    queue.Enqueue(nextComputer); 
                }
            }
        }
    }
    
    public int solution(int n, int[,] computers) {
        int answer = 0;
        bool[] visit = new bool[n]; // 방문 정보 배열 

        for(int i = 0; i < n; i++)
        {
            if (!visit[i])
            {
                BFS(computers, n, i, visit);
                answer++;
            }
        }

        return answer;
    }
}

 

 

배운점

BFS 문제를 무조건 격자 탐색으로 풀면 안된다. 

문제를 보고 격자 형태인지, 그래프 형태인지 파악하고 형태에 맞는 BFS 코드를 작성해야 한다.