JJ_blog

기본적인 BFS문제만 풀다가 살짝 응용한 문제를 마주치니 정말 어렵게 느껴졌다.. 주의할 점) -1, +1, *2를 하고 탐색을 할 때 동생의 지점보다 넘어가서 뒤로 되돌아오는 경우가 더 시간이 짧게 걸리는 예제가 존재한다. □ 소스 코드 #include #define MAX 100001 #define MIN 0 bool disList[MAX] = {false}; int seekCnt = 0; int suN, broK; void hidebfs(){ queue disQ; disQ.push(make_pair(suN,0)); int subin = disQ.front().first; int time = disQ.front().second; disList[subin] = true; while(!disQ.empty..

bfs를 살짝 응용한 문제이다. bfs를 사용할 때 무언가 움직여서 확인하려면 행,열에 대해서 배열을 생성한 후 사용하면 쉽게 아이디어를 생각할 수 있다. □ 소스 코드 #include int mazeN,mazeM; int mazeList[100][100]{0}; void bfs2178(int x,int y){ queue mazeQ; int mvX[] = {-1,1,0,0}; int mvY[] = {0,0,-1,1}; mazeQ.push({x,y}); while (!mazeQ.empty()) { x = mazeQ.front().first; y = mazeQ.front().second; mazeQ.pop(); for(int i=0;i=mazeM ) continue; if(mazeList[dX][dY] ==..

dfs 문제를 안다면 쉽게 풀 수있다 아주 쉽죠?ㅎㅎ □ 소스 코드 #include int cabN, cabM, cabK; int cabList[51][51]{0}; bool findWorm(int x, int y){ if(x=cabM) return false; if(cabList[x][y] == 1){ cabList[x][y] = 0; findWorm(x+1, y); findWorm(x-1, y); findWorm(x, y+1); findWorm(x, y-1); return true; } return false; } void cabbage(){ int testCase; scanf("%d",&testCase); for(int tC=0;tC

dfs를 이용하면 쉽게 풀지만 저장하는 배열을 동적할당하면 메모리오류가 발생한다..; □ 소스 코드 #include int inputList[25][25]{0}; int aptCntList[25]{0};//단지 별 아파트 개수 int aptCnt; // 단지 개수 int apN; bool dfs2667(int x,int y){ if(x=apN) return false; if(inputList[x][y] == 1){ inputList[x][y] = 0; aptCntList[aptCnt]++; dfs2667(x+1, y); dfs2667(x-1, y); dfs2667(x, y+1); dfs2667(x, y-1); return true; } return false; } void countNumApartment..

앞에서 풀었던 문제들(오름차순 정렬)을 한번에 해보는 문제이다. DFS, BFS 코드를 알고 있다면 손 쉽게 풀 수 있다. □ 소스 코드 #include int dbN,dbM,dbR; vector dbList[1001]; bool dbVisited[1001]{false}; void dfs1260(int v){ if(dbVisited[v]) return; dbVisited[v] = true; cout

해당 문제는 한 컴퓨터를 통해 바이러스에 감염된 컴퓨터 개수를 파악하는 문제이다. DFS를 통해 계산하면 재귀함수를 이용해서 속도적인 측면에서 느려질 것 같아 BFS를 이용하여 해결했다. 단순 BFS 문제이다. □ 소스 코드 #include int comN,comEdge; vector viList[101]; bool viVisted[101]; int virusComCnt = 0; void viFind(int v){ queue qVirus; viVisted[v] = true; qVirus.push(v); while(!qVirus.empty()){ int front = qVirus.front(); qVirus.pop(); for(int i=0;i

앞에서 풀었던 bfs 문제에서 내림차순으로 변경되었다. #include int bfsN2,bfsM2,bfsR2; vector bfsList2[100001]; bool bfsVisited2[100001]; queue bfsQueue2; int* bfsRes2; void bfs24445(int v){ int bCnt2 = 1; bfsVisited2[v] = true; bfsRes2[v] = bCnt2; bfsQueue2.push(v); while(!bfsQueue2.empty()){ int front = bfsQueue2.front(); bfsQueue2.pop(); for(int i=0;ib; } void BFS2(){ scanf("%d%d%d",&bfsN2,&bfsM2,&bfsR2); bfsRes2 = ..

bfs를 이용한 문제이다. 앞에서 풀었던 dfs와 같은 문제지만 bfs로 응용을 살짝 하면 손쉽게 풀 수 있다. 재귀함수로 인한 메모리 오류를 걱정안해도 좋다..ㅎ □ 소스 코드 #include int bfsN,bfsM,bfsR; vector bfsList1[100001]; bool bfsVisited[100001]; queue bfsQueue; int* bfsRes; void bfs24444(int v){ int bfsCnt = 1; bfsVisited[v] = true; bfsRes[v] = bfsCnt; bfsQueue.push(v); while(!bfsQueue.empty()){ int front = bfsQueue.front(); bfsQueue.pop(); for(int i=0;i

24479번 문제의 오름차순에서 내림차순으로 변경된 것 밖에 없다. #include int *dfsRes; int dfsN2,dfsM2,dfsR2; vector dfsList2[100001]; int cnt2 = 0; bool dfsVisited2[100001]{false}; void dfs24480(int v){ if(dfsVisited2[v]) return; dfsVisited2[v] = true; cnt2++; dfsRes[v] = cnt2; for(int i=0;ib; } void DFS2(){ scanf("%d%d%d",&dfsN2,&dfsM2,&dfsR2); dfsRes = new int[dfsN2+1]; for(int i=0;i

DFS를 응용한 첫 문제인데.. 실전으로 처음 접하다 보니 너무 어렵다;; 재귀함수가 100,000번 이상 중첩되다 보면 메모리 오류가 나기도 하고 cout, cin을 사용하면 대량 데이터를 입력받다 보니 시간초과가 뜨기도 한다. 여러 가지로 너무 힘든 문제다... #include int dfsN, dfsM, dfsR; bool* dfsResList; vector dfsList[100001]; int dfsRes24479[100001]; int cnt = 0; void dfs24479(int v){ if(dfsResList[v]) return; dfsResList[v] = true; cnt++; dfsRes24479[v] = cnt; for(int i=0;i