JJ_blog

해당 문제는 한 컴퓨터를 통해 바이러스에 감염된 컴퓨터 개수를 파악하는 문제이다. 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

'이것이 코딩테스트다 with 파이썬' 실전 문제 5-4입니다. 미로나 이동하는 문제는 BFS를 많이 사용하는 것 같다. 아직 미숙해서... 문제가 너무 어렵다ㅠ □ 소스 코드 #include int N,M; int** mazeInput; int mazeBFS(int x, int y){ queue mazeQueue; mazeQueue.push({x,y}); int mvX[] = {-1,0,1,0}; //상,좌,하,우 int mvY[] = {0,-1,0,1}; while(!mazeQueue.empty()){ x = mazeQueue.front().first; y = mazeQueue.front().second; mazeQueue.pop(); for(int i=0;i= N ) continue; if(maze..

'이것이 코딩테스드다 with 파이썬' 실전문제 5-3번 음료수 얼려 먹기 문제입니다. DFS를 사용하여 해결하는 문제입니다. □ 소스 코드 #include int n,m; int** input; bool dfs(int x,int y){ // 범위를 벗어나는 경우 false 리턴 if(x=m ) return false; //상하좌우를 탐색하고 찾은 경우 true 리턴 if(input[x][y] == 0){ input[x][y] = 1; dfs(x-1, y); dfs(x+1, y); dfs(x, y-1); dfs(x, y+1); return true; } return false; } void frozenJuice(){ cin>>n>>m; input = new int* [n]; for(int i=0;i

이것이 파이썬이다 with 파이썬 예제 4-4 게임개발 입니다. □ 소스 코드 #include void gameDev(){ int n,m; cin>>n>>m; cin.ignore(); int x,y,w; cin>>x>>y>>w; cin.ignore(); int **arr = new int*[n]; bool **visited = new bool*[n]; //방문한 곳 확인용 for(int i=0;i

이것이 코딩테스트다 예제 4-3 입니다. □ 소스 코드 #include void royalNight(){ string input; cin>> input; char xArray[] = {'a','b','c','d','e','f','g','h'}; char yArray[] = {'1','2','3','4','5','6','7','8'}; int x = 0; int y = 0; for(int i=0;i

해당 문제는 이것이 코딩테스트다with 파이썬 예제 4-2번 입니다. □ 소스 코드 #include void sight(){ int n; cin>>n; int endTime = n*3600 + 59*60 + 59; //입력된 시간을 초 시간으로 변경 int count = 0; //3이 포함된 경우 카운트 for(int i=0;i