슬기로운 코딩생활

문제 링크입니다 : www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net bfs 구현 문제였다. 난이도는 매우 쉬움 #include #include #include #define INF 987654321 using namespace std; int N, M; vector adj; vector visited; int dfs(int start) { queue q; q.push(start); visited[start] =..

문제 링크입니다 : www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 브루트 포스 + BFS 문제였다. 보드의 사이즈가 굉장히 작아서 브루트 포스로도 해결가능한 문제였다. 입력 사이즈가 작으면 언제나 브루트 포스를 최우선 고려하자 #include #include #include using namespace std; const int dy[4] = {0, 0, -1, 1}; const int dx[4] = {-1, 1, 0, 0}; int N, M; vector board..

문제 링크입니다 : www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4= N - 1) return false; for(int i = 0; i = N) continue; if(!canMove(ny, nx, cIsRow)) continue; if(visited[ny][nx][cIsRow]) continu..

문제 링크입니다 : 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 BFS 문제였다. Board에서 이동하는 기본적인 BFS 문제 유형은 위치만 고려..

문제 링크입니다 : programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 알고리즘 자체는 BFS로 굉장히 쉽다. 하지만 구현이 상당히 어렵기 때문에 시간이 꽤 오래 걸렸다... 실수를 줄인다면 시간을 3분의 1 이하로 줄일 수 있을 거 같은데... 실수를 줄이는 연습부터 해야겠다. 그림을 그리면서 하니까 실수가 조금 줄어드는 것 같다. 그림을 그리면서 실수를 줄이자. #include #include #include #include using namespace..

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr bfs 문제였다! #include #include #include using namespace std; const int dy[4] = {0, 0, -1, 1}; const int dx[4] = {-1, 1, 0, 0}; vector visited; int bfs(const vector& ..

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 그래프 문제! BFS로 순회했다! #include #include #include #include using namespace std; vector adj; vector visited; bool canChange(const string& str1, const string& str2) { int cnt..

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 그래프 문제였다. 그래프나 트리에서 깊이별로 탐색하고 싶다면 bfs를 쓰면 된다. #include #include #include using namespace std; vector adj; vector visited; vector bfs(int start) { queue q; q.push(start); visited[start] = true; vector ret; while(!q.empty()) { int qSi..