Dev:P

문제 이번에 다뤄볼 문제는 7569번 문제 '토마토'입니다. 토마토 문제에서 연습해야하는 key-point는 BFS입니다. BFS는 너비 우선 탐색을 뜻하는데요. 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다. 이 문제는 7576번(토마토) 문제에서 살짝 응용 된 문제입니다. 기존에서는 x,y에 의한 방향 이동만 존재했다면 이 문제에서는 z축 방향의 이동을 생각해 주면 됩니다. 그 외 문제를 푸는 방식은 7576번과 같습니다. 백준 알고리즘 7576번 (토마토) 문제 이번에 다뤄볼 문제는 7576번 문제 '토마토'입니..

문제 이번에 다뤄볼 문제는 7576번 문제 '토마토'입니다. 토마토 문제에서 연습해야하는 key-point는 BFS입니다. BFS는 너비 우선 탐색을 뜻하는데요. 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다. BFS를 활용하여 토마토가 익어나가는것을 탐색 할 수 있으며 탐색되어 익게되는 토마토의 값을 1로 map에서 바꿔줍니다. visited 2차원 배열에 탐색 횟수를 증가시켜가며 저장해 줍니다. 모든 탐색이 끝난 후 map에 아직 익지 않은 토마토(0)가 존재한다면 이는 토마토가 모두 익지 못하는 상황이므로 예외처..

문제 이번에 다뤄볼 문제는 1527번 문제 '금민수의 개수'입니다. 금민수의 개수 문제에서 연습해야하는 key-point는 큐입니다. 큐(queue)란 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 뜻합니다. A와B사이에 존재하는 모든 금민수의 개수를 구하는 문제 입니다. 해당 문제의 test case 값 범위가 1,000,000,000이기 때문에 변수를 선언알때 long long int 를 활용하였습니다. 큐에 기본 금민수인 4 와 7을 초기값으로 넣어놓고 이들 각각의 자리수를 한 자리씩 올려주며 4,7을 더해줍니다. 그 후 바꾼 수를 큐에 넣습니다. ex) 4,7 -> 44,47,74,77 -> 444,..

문제 이번에 다뤄볼 문제는 1526번 문제 '가장 큰 금민수'입니다. 가장 큰 금민수 문제에서 연습해야하는 key-point는 큐입니다. 큐(queue)란 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 뜻합니다. 금민수는 4와 7로만 이루어진 수를 말합니다. 입력받은 n을 4가 될때까지 1씩 줄여나가며 해당수를 각 자리수 별로 잘라 큐에 집어 넣습니다. 큐를 하나씩 빼며 4혹은 7을 갖는 수 라면 count값을 증가시켜줍니다. 큐에 들어갔던 자리수의 갯수(rear)가 count된 수와 같다면 이는 4와 7로만 이루어진 수 이므로 금민수입니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(..

문제 이번에 다뤄볼 문제는 7562번 문제 '나이트의 이동'입니다. 나이트의 이동 문제에서 연습해야하는 key-point는 BFS와 큐입니다. BFS는 너비 우선 탐색을 뜻하는데요. 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다. 큐(queue)란 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 뜻합니다. 나이트가 이동 할 수 있는 8방향을 dirX,dirY배열에 입력합니다. 그리고 나이트의 다음 탐색 가능 위치를 큐에 넣..

문제 이번에 다뤄볼 문제는 1697번 문제 '숨바꼭질'입니다. 숨바꼭질 문제에서 연습해야하는 key-point는 큐입니다. 큐(queue)란 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 뜻합니다. visited라는 배열을 하나 만들어 방문 된 위치는 재탐색을 하지 않도록 하였습니다. 그리고 큐를 활용하여 문제를 해결하였는데요. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include using namespace std; int visited[100001]; int q[100001]; int front = 0, rear = 0; int tmp_f = 0, tmp_r = 0; ..

문제 이번에 다뤄볼 문제는 2468번 문제 '안전 영역'입니다. 안전 영역 문제에서 연습해야하는key-point는재귀함수입니다. 재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업울 수행하는 방식의 함수를 뜻합니다. real_map과 map 이라는 2차원 배열을 두개 만들어 map의 값은 영역 체크가 끝나게 되면 0으로 바꿔주어 다시 탐색하지 않도록 하기 위함이고 real_map의 경우 처음 들어온 초기값을 유지하고 있는 2차원 배열입니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include using namespace std; int real_map[101][101]; int map[101][101]; int dirX[4] = { 0, 0, 1, -1 }; int ..

문제 이번에 다뤄볼 문제는 1012번 문제 '유기농 배추'입니다. 유기농 배추 문제에서 연습해야하는 key-point는재귀함수입니다. 재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업울 수행하는 방식의 함수를 뜻합니다. 배추가 최초 확인 되었을 경우 b_count값을 증가시켜준뒤 재귀로 들어가 인접한 배추들을 다시 탐색하지 않도록 2로 값을 바꿔줍니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include using namespace std; int map[51][51] = {0}; int dirX[4] = {0,0,-1,1}; int dirY[4] = {-1,1,0,0}; int xx = 0, yy = 0; int t, m, n, k; int b_count = 0;..

문제 이번에 다뤄볼 문제는 4963번 문제 '섬의 개수'입니다. 섬의 개수 문제에서 연습해야하는 key-point는 재귀함수입니다. 재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업울 수행하는 방식의 함수를 뜻합니다. 문제를 읽어봤을때 한 정사각형과 가로, 세로 또는 대각선으로 가는 방향 까지도 고려해야 하므로 총 8가지 방향을 탐색하게 합니다. 재귀를 통해 구현 했으며 최초로 발견되는 육지가 발생하면 i_count값을 증가시켜준뒤 재귀로 들어가 이어지는 육지들의 값을 2로 바꿔주어 다음번에 다시 탐색하지 않게 합니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include using namespace std; int map[52][52]; const int dsize..

문제 이번에 다뤄볼 문제는 2178번 문제 '미로 탐색'입니다. 미로 탐색 문제에서 연습해야하는 key-point는 BFS입니다. BFS는 너비 우선 탐색을 뜻하는데요. 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다. 문제를 살펴보면 N을 소인수분해 했을때 나타날 수 있는 인수중 가장 큰 값은 루트N입니다. 따라서, 2부터 루트N까지 for문을 돌면서 N을 나눌 수 있다면 계속 나눠주면 됩니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include #include #pragma wa..