728x90
728x90
'Algorithm(SWEA)' 카테고리의 다른 글
[C++] SW 역량테스트 - 로봇청소기(DFS) (0) | 2021.03.21 |
---|---|
[C++] SWEA - 2819. 격자판의 숫자 이어 붙이기 - DFS (0) | 2021.01.17 |
[C++] SW 역량테스트 - 로봇청소기(DFS) (0) | 2021.03.21 |
---|---|
[C++] SWEA - 2819. 격자판의 숫자 이어 붙이기 - DFS (0) | 2021.01.17 |
[C++] SW 역량 테스트 - 아기 상어 (구현 / BFS) (0) | 2021.03.25 |
---|---|
[C++] SWEA - 2819. 격자판의 숫자 이어 붙이기 - DFS (0) | 2021.01.17 |
문제 링크 : 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; }
[C++] SW 역량 테스트 - 아기 상어 (구현 / BFS) (0) | 2021.03.25 |
---|---|
[C++] SW 역량테스트 - 로봇청소기(DFS) (0) | 2021.03.21 |