mintuchel mintuchel

3차원 토마토인데 이것도 푸는 방식은 2차원 토마토와 동일함. day를 pair 와 같이 넣어줌으로써 while 문안에 bfs를 돌리면서 day를 count 하지 않아도 되게끔 함.이게 훨씬 나은 방식인듯?? #include #include #include #define SIZE 101using namespace std;int map[SIZE][SIZE][SIZE];int visited[SIZE][SIZE][SIZE];int M, N, H;int dy[4] = {-1, 1, 0, 0};int dx[4] = {0, 0, -1, 1};int dz[2] = {-1, 1};queue, int>> q;void solve(){ int ans = -1; while (!q.empty()) { ..

치즈를 한턴의 bfs를 돌때 녹이지 않는게 중요하다.bfs 돌때 녹여줘야하는 곳에 대한 정보를 저장해둔 후 bfs가 끝나고 녹여줘야한다. 치즈가 모두 없어질때까지 해야하므로치즈 유무를 파악하면서 bfs를 계속 돌리면 된다 #include #include #include #include #define SIZE 101using namespace std;int N, M;bitset map[SIZE];int dy[4] = {-1, 0, 0, 1};int dx[4] = {0, -1, 1, 0};int count_cheese(){ int cnt = 0; for (int i = 0; i > q; int cheese_touch[SIZE][SIZE] ={0,}; bitset visited[SIZE]..

재귀 돌려서 풀었다. 중간에 재귀 내 코드를 바꾼 부분은 이 두 부분 때문이다. 1. visited 했다고 못가는 것이 아니라는 거 처음에는 visited 했으면(에어컨바람이 한번 지나간 곳이면) 아예 더 이상 진행 못하게 했는데 만약 다른 방향으로 에어컨 바람이 진행되고 있었으면 visited 했던 곳도 또 갈 수 있다. 따라서 방문했다고 바로 return 해버리는 것은 옳지 않다. 2. 에어컨인 곳이면 return 해도 된다는거 1번만 바꾸고 냈는데 60%에서 시간초과가 떴다. 그래서 생각을 해보니 만약 에어컨이 있는 곳에 도달했으면 탐색하지 않아도 된다. 왜냐하면 에어컨이 있는 위치는 모든 방향으로 바람이 나가는 곳이기 때문에 내가 굳이 지금 특정 방향으로 진행을 안해줘도 해당 방향으로 진행이 될 ..

아래처럼 queue> q 를 사용하고 while 문으로 감싸서 bfs를 돌린 이유는 bfs 한번 돌릴때마다 day++를 해주기 위함이었다. 하지만 다시 생각해보니 day 자체를 queue의 pair 와 같이 넣어주면 while 문으로 감쌀 필요도 없었다.#include #include #define SIZE 1001using namespace std;int map[SIZE][SIZE];int M, N;int dy[4] = {-1, 1, 0, 0};int dx[4] = {0, 0, -1, 1};// ((y,x), day)queue, int>> q;void solve(){ int ans = -1; int cury, curx, nexty, nextx; while (!q.empty()) {..

최근에 DFS 백트래킹만 풀어서 BFS 복습하려고 품 visited 배열을 bool로 하는 것보다 bitset로 하는게 훨씬 공간복잡도와 시간복잡도 측면에서 좋다. bitset도 direct memory access가 가능한 자료구조라 쓸 가치가 있다. #include #include #include #include #include #define SIZE 100001 using namespace std; int N, M, R; vector arr[SIZE]; int ans[SIZE]; bitset visited; void BFS(int R) { // 초기설정 visited.set(0); int cnt = 1; queue q; visited[R] = 1; q.push(R); ans[R] = cnt++; w..

그냥 전형적인 BFS 문제BFS는 재귀보단 내부적으로 queue 써서 돌리는게 더 직관적이다 시작점을 희소행렬로 저장해두고 미리 시작점들을 queue에 넣고 BFS 돌려주면 됨 #include #include #include #include #define SIZE 1001using namespace std;bitset map[SIZE];bitset visited[SIZE];vector> v;int dy[4] = { 0,-1,1,0 };int dx[4] = { -1,0,0,1 };int M, N;void solve() { queue> q; // 시작점 모두 넣기 for (int i = 0; i = M || newx >= N || visited[newy][newx]) continue; // 아직 방문하지..

지금까지 푼 DFS/BFS 문제 중 제일 난이도 있는 문제였음풀면서 BFS뿐만 아니라 그 외 것들을 구현하는데 생각을 더 해야했음 1. 우선 가장 중요한건 BFS돌면서 빙하를 녹이면 안된다는거임 왜냐하면 하면서 녹이면 그 다음꺼가 바다랑 맞닿는 면의 개수에 영향을 끼치기 때문그래서 녹일 양을 따로 저장해야함 2. 그 다음으로 중요한게 2분할 됐냐 확인하는거임 이건 모든 원소 다 돌면서 visited 됐는지 확인하고 BFS돌리고 그러면서 cnt++ 해서 판단가능함 BFS 한 턴으로 다 돌면 정상이고BFS가 두 턴 이상 나오면 breakBFS가 0이면 다 녹았다는 뜻이므로 종료 BFS가 0번이면 그건 다 녹을때까지 cnt가 두 번 이상 안나왔다는 뜻이므로 바로 종료해주면 된다  for (int i = 0; ..

BFS에서는 이미 방문한 곳은 최소값이 보장되어있음을 이해하는게 중요visited[newy][newx] = 1 이면 해당 장소는 최소값이 보장되어있다초반에 DFS로 하다 시간초과로 틀린 문제 이 문제는 BFS 로 풀어야함DFS는 첫번째 접근이 최단거리임을 보장해주지 않으므로목표까지 가는 모든 경우의 수를 종합하여최소값을 뽑아내야하므로 시간복잡도가 훨씬 큼 하지만 BFS는 첫 해가 최단거리임을 보장해줌따라서 방문을 했으면 최신화하고 아니면 최단거리가 이미 나온 경우이므로 안도는게 맞음 왜냐하면 BFS는 각 레벨에 있는 노드들을 순차적으로 큐에 넣고 빼서 검사하는 식이므로큐에 들어가는 노드들의 레벨은 전 노드 레벨 + 1 로 +1 씩 되어가는 구조이기 때문. 그래서 찾고자하는 해의 첫번째 등장이 곧 답이고 ..