728x90
728x90

 

 

nanyoungkim.tistory.com/91

 

[C++] 백준 16236번 - 아기 상어 (구현)

문제 링크 : www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마

nanyoungkim.tistory.com

 

 

728x90
728x90

nanyoungkim.tistory.com/83

 

[C++] 백준 14503번 - 로봇청소기(DFS)

문제 링크 : www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으

nanyoungkim.tistory.com

 

 

728x90
728x90

문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

 

 

 

 

접근 방법

재귀를 이용한 DFS로 풀었다. set 자료구조로 삽입시 중복이 되지 않게 했다.

테스트 케이스가 반복되므로 매 테스트케이스가 끝날때마다 초기화를 잘 해줘야 에러가 안 뜬다. 주의하자!

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int map[4][4]={0};

//위,오,아,왼
int dr[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};

vector<int> nVec;
set<int> ansVec;

void DFS(int r, int c, int toPick){
    
   
    if(toPick==0){
        int num = nVec[0]*1000000+nVec[1]*100000+nVec[2]*10000+nVec[3]*1000+nVec[4]*100+nVec[5]*10+nVec[6];
        
        ansVec.insert(num);
        return;
    }
    
    
    for(int i=0; i<4; i++){
        
        int nr=r+dr[i];
        int nc=c+dc[i];
        
        if(nr>=4 || nr<0 || nc>=4 || nc<0) continue;
        
        nVec.push_back(map[nr][nc]);    //next 지점이 범위 안에 들어오면 push
        DFS(nr,nc,toPick-1);
        nVec.pop_back();				//원상복구
    }
}

int main(){

    int T;
    cin >> T;
    
    int ans=0;
    for(int test_case = 1; test_case <= T; test_case++){
        
         for(int i=0; i<4; i++){
           for(int j=0; j<4; j++){
               cin>>map[i][j];
           }
         }
        
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                nVec.push_back(map[i][j]);          //첫 시작지점 넣음
                DFS(i,j,6);
                nVec.clear();					 //초기화 필수

            }
        }
        
        cout << "#" << test_case << " " << ansVec.size() << "\n";
        
        //초기화 필수
        ans=0;
        ansVec.clear();
        nVec.clear();
        
    }
    
    return 0;
}

 

 

 

 

처음에는 set이 아닌 vector를 이용해서 find()를 통해 중복검사를 했는데 제한시간 2초를 넘겨서 시간초과가 떴다. 그래서 set으로 바꿔봤는데 바로 통과됐다.

if(toPick==0){
        int num = nVec[0]*1000000+nVec[1]*100000+nVec[2]*10000+nVec[3]*1000+nVec[4]*100+nVec[5]*10+nVec[6];
       
        if(find(ansVec.begin(),ansVec.end(),num) == ansVec.end()){
            ansVec.push_back(num);
        }
        return;
}

 

 

728x90

+ Recent posts