Little Jay

트리를 활용한 문제이다. 사실 트리 문제가 나오면 DFS를 활용하는 것이 정배라고는 하지만 이 문제는 단순히 BFS를 통해서 문제를 풀 수 있었다. 1번 Node는 고려하지 않으므로, 1번 Node에서 출반하여 BFS 탐색을 수행하면 문제가 풀린다. 문제는 항상 root node가 1이 아니기 때문에 입력에서 양방향 인접리스트로 받았는데, 이제 visited한 것을 잘 처리해주면 된다. #include #define endl '\n' #define pii pair using namespace std; int n; vector tree[100001]; bool visited[100001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)..

BFS를 기반으로 하는 문제이다. 단순히 BFS를 두번 돌리면 되는데, 첫 번째는 정상적인 BFS로, 두 번째는 R==G일때도 통과되게 만들면 된다. #include #define endl '\n' #define pii pair using namespace std; int t; int n; char graph[101][101]; bool visited[101][101]; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; int bfs(int x, int y, bool eye) { visited[x][y] = true; char target = graph[x][y]; queue q; q.push({ x, y }); while (!q.e..

간단한 bfs문제. https://euler.synap.co.kr/quiz=3 입력받아야 하는 수가 좀 많아서 그렇지 bfs만 돌리면 간단하게 풀 수 있는 문제였다. #include #define endl '\n' using namespace std; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; int display[1920][1080]; bool visited[1920][1080]; int bfs(int x, int y) { visited[x][y] = true; queue q; q.push({ x, y }); int size = 1; while (!q.empty()) { auto cur = q.front(); q.pop();..

코로나 확진 후 집에서 공부가 되지 않는 스타일이라 주구장창 놀기만 한 것 같다. 슬슬 블로그 운영 다시 해야겠다. 간단한 BFS문제였지만 오타때문에 맞왜틀을 1시간동안 하고 있던 문제다. 3차원 배열을 활용해서 벽을 부쉈으면 [][][1]쪽으로 이동해서 그쪽에서 부터 BFS를 돌리면 된다. 코딩 스타일이 cur.first.first 이렇게 전부 다 쓰는 스타일이라 여기서 까딱 실수해버리면 항상 맞왜틀 하고 있는 것 같다... #include #define endl '\n' #define pii pair using namespace std; int graph[1001][1001]; int visited[1001][1001][2]; int n, m; const int dx[] = { 1, -1, 0, 0 ..

실제 뿌요뿌요 게임을 구현하는 문제였다. 아이디어는 이렇다 4개 이상의 같은 색깔의 슬라임(?)이 모이면 터지고 1연쇄가 일어난 후 뿌요들이 아래로 중력에 의해 내려온다. 이 문제를 풀때 간과했던 것은 한 번에 터뜨릴 수 있는 것들은 한번에 터지고 이는 1 연쇄이다. 그래서 한번에 2개의 그룹이 터져도 2연쇄가 아니라 1연쇄이다. 이 부분을 제외하면 재밌게 풀었던 문제이다. #include #include #define endl '\n' using namespace std; char graph[12][6]; bool visited[12][6]; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; int ans = 0; //일반 bfs ..

간단했던 BFS 문제였는데 멍청하게 BFS 수행 조건을 잘못 줘서 30분동안 맞왜틀 하고 있던 문제였다. 특별한 로직은 따로 없었고 양의 수 > 늑대 수 일때만 양의 수를 업데이트 시키는 것만 잘 파악했다면 크게 거렵지는 않았다. #include #define endl '\n' using namespace std; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; char board[255][255]; bool visited[255][255]; int r, c; int wolves = 0, sheep = 0; void bfs(int x, int y) { queue q; q.push({ x, y }); visited[x][y] = tr..

발냄새라는 단어를 듣고 기계공학과를 떠올린 나...... 최단경로를 찾는 문제이다. 주어진 간선의 weight 정보가 없고, 단순히 출발점으로부터 얼마나 떨어져있는지 물어보는 문제이기 때문에 충분히 BFS으로 풀 수 있다고 판단을 했다. 조심해야 할 점은 그래프가 무향그래프라는 점이다. 그렇기 때문에 입력을 받고, 그래프에 넣을 때 양쪽의 정보를 넣어주어야 문제를 편하게 풀 수 있다. 이런 결의 문제의 경우 인접행렬로 처음에 배열을 int adj[20010][20010]이라고 정의를 하게되면 배열의 사이즈가 4 * 20010 * 20010으로 초기에 너무 커질 것 같아 인접리스트로 푸는것이 더 나은것 같다고 판단했다. #include #define endl '\n' #define INF 987654321..

인접행렬로 문제를 푸는 것을 선호하는데, 이렇게 인접 리스트로 푸는게 오랜만이라 시간이 좀 걸렸다. 항상 느끼는 거지만 인접행렬이 더 편한 것 같다. #include #define endl '\n' #define MAX 100005 using namespace std; int n, m, init; vector v[MAX]; bool visited[MAX]; int solve() { int cnt = 0; queue q; q.push(init); visited[init] = true; while (!q.empty()) { auto current = q.front(); q.pop(); if (!v[current].size()) { return cnt; } if (visited[v[current][0]]) b..

입력받는것을 계속 int로 받다가 실패했다. 띄어쓰기가 없는 것은 char이나 string으로 받아야 하는 것에 유의하자. n-1일때 return true 해야하는데 m-1로 계속 써서 실패했다. 항상 조건을 잘 보도록 하자. #include #define endl '\n' using namespace std; int n, m; int board[1005][1005]; bool visited[1005][1005]; const int dx[4] = { 1, -1, 0, 0 }; const int dy[4] = { 0, 0, 1, -1 }; bool bfs(int y, int x) { visited[y][x] = true; queue q; q.push({ y, x }); while (!q.empty()) {..

BFS로 구현했다. (DFS 싫어) #include #define endl '\n' using namespace std; bool arr[51][51]; bool visited[51][51]; const int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 }; const int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 }; int w, h; int bfs(int x, int y) { if (arr[x][y] == 0) return 0; if (visited[x][y]) return 0; queue q; q.push({ x, y }); visited[x][y] = 1; while (!q.empty()) { auto current = q.front(); q.pop();..