댄코 - 댄싱코딩

문제보기1.10진수를 4비트 2진수로 변경 2.BFS로 뚫려있는 부분만 큐에 넣어 방 도출해서 각 방에 번호 붙임 => 방의 갯수, 가장 넓은 방 넓이 3.0,0부터 오른쪽 아래까지 현재 좌표에서 오른쪽, 아래쪽을 검사 하면서 방번호가 다르면 두 방의 넓이를 더한것 중 가장 큰것=>하나의 벽을 제거해서 얻을 수 있는 가장 넓은 방의 크기 #include #include using namespace std;int dy[4] ={1,0,-1,0};int dx[4] ={0,1,0,-1};int map[51][51]={0};int check[51][51]={0};int N,M;int checkNum = 1;int* getBinary(int n){ static int tp[4]; for(int i = 0;i

문제보기일반적으로 빙산문제와 같지만 배열의 크기가 1500*1500이기 때문에 다른 솔루션이 필요하다. 우선 전처리로 각 빙산이 몇일이 지나면 녹게 되는지 water배열에 저장하고 이를 이용한다.waterBFS에서는 이 water배열을 만들면서 모든 빙산이 녹은 날짜를 리턴한다.BFS에서는 백조 두마리가 만날 수 있는지 검사한다. main에서는 0부터 모든 빙산이 녹은 날짜 사이에 백조가 만날 수 있는 가장 최소의 날짜를 이분탐색으로 구해 답을 도출한다. #include #include using namespace std;int N,M;int map[1501][1501];int numMelt = 0;int numVisit = 1;int check[1501][1501]={};int water[1501][1..

문제보기 맥북 충전기를 두고와서 윈도우인 집 컴퓨터에서 웹 IDE를 사용해서 풀다보니 디버깅이 어려워서엉뚱하게 입력부분에서 헤멨던 문제.BFS를 사용해서 구간별로 늑대와 양의 수를 구한 후 양이 많으면 양의 수를 리턴,늑대가 많으면 늑대 수 * -1을 해준다. 메인에서 각각 양의수와 늑대 수 (*-1)로 답을 도출한다. #include using namespace std;char map[251][251]={};int check[251][251]={};int dy[4] = {1,0,-1,0};int dx[4] = {0,1,0,-1};int N,M;int BFS(pair n){ queue q; q.push(n); int wolf=0; int sheep=0; while(!q.empty()){ int y = q..

문제보기"두 원이 인접하려면 두원의 반지름의 합이 두 원의 중심사이의 거리보다 크거나 같아야한다" 라는 조건으로 우선 진영끼리 인접하고 있는지 알 수 있는 인접리스트/행렬을 만든 후 BFS/DFS를 돌려서 문제를 해결한다. #include #include #include #include using namespace std; float getDistance(pair n, pair m){ return (n.first - m.first) * (n.first - m.first) + (n.second - m.second) * (n.second - m.second);} int countCircleGroup(){ queue q; vector vec; int r[3001]; vector link[3001]; int c..

BFS를 사용하면 쉽게 풀 수있는 문제였다. 처음에 토마토가 비어있는 부분이 있으면 (배열중 들리지 않은곳이 있으면) 무조건 모두 익지 않은 경우라고 체크해서 -1을 출력하고 틀렸었다.처음 주어진 익은 토마토를 큐에 전부 넣는다 check[x][y]에는 토마토가 익은 날을 저장한다. 인접한 토마토는 check[x][y] 다음날에 익으므로check[nx][ny] = check[x][y]+1이다. check[x][y]중 가장 큰 수가 토마토가 모두 익은 날이다. #include #include using namespace std; int main(){ int box[1001][1001]; int check[1001][1001]; queue q; int N,M; scanf("%d %d",&N,&M); for(..

그래프에 있는 사이클을 구하는 문제다.i번째 인덱스를 고정해놓고 1 부터 검사한다. j = arr[i]로 초기화하고 이때 j(다음으로 이어질 숫자) 와 i(사이클의 첫번째 숫자)가 같을 때까지 j = arr[j]로 업데이트한다. 검사한 인덱스 에는 1을 대입해 중복 검사를 하지 않도록 한다. j 와 i 가 같아지면 순열 사이클이 형성된것이므로 res에 1을 추가한다. #include using namespace std; int main(){ int T,N; int arr[1000]; int check[1000] = {}; int j = 0,res = 0; scanf("%d",&T); while(T > 0){ res = 0; j = 0; scanf("%d",&N); for(int i = 1;i