소근소근

Lv3 . 프로그래머스 경주로 건설 (2020 카카오 인턴십) 문제 설명 https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 그렇게 어려운..

level3 지만 bfs로 간단하게 해결할 수 있는 문제였다. 오히려 level2보다 더 쉬운거 같기도 하고 ,.? dog -> dot 처럼 한 char만 바꿀 수 있다. 주어진 words의 문자들의 길이는 모두 동일하다고 조건이 주어졌기 때문에 단순히 두 문자열을 앞에서부터 비교하여 다른 char가 하나만 있을때 변환이 가능하도록 한다. #include #include #include #include #include #include #include using namespace std; bool able = false; queue q; map visit; int compchar(string a, string b){ int len = a.length(); int cnt =0; for(int i=0;i

BFS/DFS 분류에 있는 문제였지만, 분리집합으로 풀었다. 컴퓨터 두대가 연결 되면 같은 네트워크(같은 집합)으로 분류되기 때문이다. 연결된 컴퓨터 두대는 union해서 같은 집합으로 보고, 마지막에 집합의 개수를 출력하면 된다. #include #include #include #include #include using namespace std; int parent[200]; map m; int Find(int x){ if(x==parent[x]) return x; return parent[x] = Find(parent[x]); } void Union(int x, int y){ int px = Find(x); int py = Find(y); if(px != py){ parent[px] = py; } }..

bfs를 이용하면 쉽게 해결할 수 있는 문제이다. queue에 -num , num 을 더해주고 큐에 push하면서 반복문을 돌고, target 에 도달하면 answer를 증가시켜서 카운트한다. #include #include #include #include #include #include #include using namespace std; queue q; int solution(vector nums, int target) { int ans = 0; q.push({0,-nums[0]}); q.push({0,nums[0]}); while(!q.empty()){ int now_idx = q.front().first; int total = q.front().second; q.pop(); if(now_idx =..