TIL day 31

1. 코딩테스트

---

오늘은 프로그래머스 level 2 전력망을 둘로 나누기를 풀었습니다.

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

프로그래머스

• 뭘로 풀지?
  • 트리 구조 + 완전 탐색 + bfs탐색
  • 모든 경우의 수를 돌면서 트리 구조로 주어진 데이터를 벡터를 통해서 데이터를 저장한 다음, bfs를 통해서 트리의 갯수를 세서 풀었습니다.
  • 좀 더 자세한 과정
    • 모든 wires의 경우를 돌면서 한 가지씩 끊어서 adj라는 벡터에 데이터를 저장했습니다. 
      • idx라는 변수를 통해 adj에 넣지 않을 데이터를 구분해 주었습니다.
      • n이 100 이하였기 때문에, 그냥 모든 경우의 수를 돌아도 괜찮을 것 같다고 생각했습니다.
    • 이후 bfs를 통해서 연결된 갯수를 구했습니다.
      • 시작점은 1로 해서 탐색을 하였고, 일반적인 bfs를 진행하였습니다.
      • 방문하지 않은 곳이라면 ans라는 변수에 +1을 해서, 연결된 노드의 갯수를 구해서 return 하였습니다.
    • bfs의 결과와 전체 간선의 갯수를 통해 간선의 차이를 구했습니다.
      • temp1은 bfs의 결과를 저장하였고, total은 전체 간선의 갯수입니다.
      • temp2 = total - temp1 - 1; 을 통해 bfs로 탐색하지 않은 간선의 갯수를 구했습니다.
      • answer = min(answer, abs(temp1 - temp2)); 를 통해 간선의 갯수가 최소가 되는 값을 구해주었습니다.
• 코드

#include <string>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

vector<int> adj[102];
int vis[102];

int bfs(vector<int> adj[])
{
    int ans = 0;
    fill(vis, vis + 102, 0);
    
    queue<int> q;    
    q.push(1);
    vis[1] = 1;
    
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        
        for(int nxt : adj[cur])
        {
            if(!vis[nxt])
            {
                q.push(nxt);
                vis[nxt] = 1;
                ans++;
            }
        }
    }
    return ans;
}

int solution(int n, vector<vector<int>> wires) 
{
    int answer = INT_MAX;
    int total = wires.size();
    int idx = 0;
    
    while(idx < wires.size())
    {        
        for(int i = 0; i < 100; ++i)
            adj[i].clear();
        for(int i = 0; i < wires.size(); ++i)
        {
            if(i == idx)
                continue;
            adj[wires[i][0]].push_back(wires[i][1]);
            adj[wires[i][1]].push_back(wires[i][0]);
        }   
        
        int temp1 = bfs(adj);
        int temp2 = total - temp1 - 1;
        
        answer = min(answer, abs(temp1 - temp2));                
        idx++;
    }
    return answer;
}

 

 

 

2. 과제

---

과제 ch6을 완료하고, 제출하였습니다. 

• 깃허브에 readme 작성도 하고, 시연 영상도 찍어서 업로드 하였습니다.

https://github.com/GBL22M/SCC_CH3-6

GitHub - GBL22M/SCC_CH3-6

• 정리하는 과정에서 Data Table을 처음 사용해 보아서 관련 내용도 정리해 보았습니다.

https://gbleem.tistory.com/59

Unreal Engine - Data Table