leebaek

문제 테스트 케이스마다 섬의 개수를 구하는 문제 -섬은 1로 표시, 바다는 0으로 표시 -섬은 상하좌우, 대각선으로 연결될 수 있음 생각 일반 BFS 문제에선 상하좌우만 탐색했었는데, 이 문제는 상하좌우 뿐만 아니라 대각선까지 탐색해야할 칸이 확장되었음 방향 반복문 돌릴 때, 기준 칸을 둘러싸고 있는 8칸 모두 확인하면 됨 문제풀이 1.w, h가 0 0이 나오면 종료되는 반복문 실행 2.board를 돌다가 방문하지 않은 섬이 나오면 큐에 푸쉬해줌 + 방문표시 3.기준 칸을 둘러싼 칸에 방문하지 않은 섬이 나오면 큐에 푸쉬해줌 + 방문표시 -dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1} | dy[8] = {1, 1, 1, 0, 0, -1, -1, -1) 4.섬의 개수 반환 후 출력 코드 ..

문제 적록색약이 아닌 사람이 보는 영역의 개수와 적록색약인 사람이 보는 영역의 개수를 구하는 문제 -RGB로 이루어진 배열에서 적록색약인 사람은 R, G를 구분하지 못하고 같은 색으로 봄 생각 적록색약이 아닌 사람은 일반 BFS 탐색을 돌려서 영역의 개수를 구하면 됨 적록색약이면 기준이 되는 칸과 상하좌우칸 모두 B가 아닐 경우에 푸쉬해줌 -R, G or G, R인 경우 *코드가 조금 지저분하긴 한데 구글링 안하고 푼거는 처음인듯 ... 얏호 문제풀이 1.(0, 0)부터 배열을 돌면서 방문하지 않은 칸이라면 BFS탐색 시작 2.적록색약이 아닌 경우 -기준이 되는 칸과 상하좌우의 칸의 색깔이 같을 경우 -큐에 푸쉬 + 방문표시 3.적록색약인 경우 -기준이 되는 칸과 상하좌우의 칸의 색깔 둘다 B가 아닌 경..

문제 수빈이가 동생의 위치까지 가는데 걸리는 최소 시간을 구하는 문제 생각 bfs 탐색에 3가지 방법(x+1, x-1, x*2)으로 이동한 후, 가장 빠르게 목적지에 도달했을 때의 시간을 출력하면 됨 문제풀이 1. BFS탐색 -1) 만약 x*2 위치에 방문하지 않았고, x*2가 범위에 벗어나지 않는다면 -2) 만약 x+1 위치에 않았다면, -3) 만약 x-1 위치에 않았다면, -큐에 위치(*2, +1, -1)와 시간(+1)을 푸쉬함 + 방문표시 2. 동생 위치에 도달하면 시간 출력하고, 반복문 종료 코드 #include #include #include using namespace std; #define X first #define Y second int vis[100001]; int N, K; int m..

문제 모눈종이에서 직사각형이 차지하지 않는 영역 개수와, 각 영역의 칸 개수를 출력하는 문제 생각 모눈종이의 좌표가 배열이랑 배치가 달라서, 직사각형 영역의 칸에 표시를 어떤식으로 해야할지 생각해봄 N, M 바꾸니까, 시계방향으로 90도 회전하면서 원래의 맵이랑 내용물은 같음 반복문 돌릴 때 M|N 대신 N|M으로 하면 해결! 문제풀이 1.직사각형 영역이면 board에 1표시 -주어진 왼쪽 아래 좌표, 오른쪽 위 좌표 이용함( 왼.x~ 오.x-1 & 왼.y ~ 오.y-1 ) 2. 직사각형 영역이 아니면 BFS 탐색 -영역의 넓이를 구하기 위해 푸쉬될 때마다 cnt++ -cnt를 벡터 Cnt에 push해줌 3. 벡터를 오름차순 정렬해줌 -sort( 벡터 시작, 벡터 마지막 ) 사용 코드 #include #..