문제 링크[2573 빙산]접근배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 시간 제한은 1초이고, N, M은 3 이상, 300 이하이다.배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. → 뭔가 조건을 치면 단순 탐색을 해도 될 것 같다.시간 복잡도빙하를 탐색하는 시간 복잡도는 배열 전체를 순회하면서 빙하(1 이상의 정수로 표현된 칸)를 탐색하거나, DFS 또는 BFS를 이용하여 연결된 빙하 영역을 탐색하는 경우를 고려해야 한다.배열 순회 O(N×M)배열 크기는 N×M이며, 최악의 경우 배열 전체를 순회해야 한다.따라서 순회에 걸리는 시간은 **O(N×M..
문제 링크[2146 다리 만들기]접근섬을 찾는다. (섬들은 각각 구별한다.)BFS내부 count를 지정해서 섬을 1, 2, 3… 등으로 매긴다.한 섬에서, 다른 섬과 이어지는 가장 가까운 장소를 찾는다.각 좌표마다 BFS가장 가까이 있는 섬 좌표까지의 거리를 저장한다.각각 거리를 계산해 최소값을 출력한다.섬 간 거리들을 저장한 배열을 정렬해서 최소값을 출력한다.코드 (O(N^4))/* * 1. 섬을 찾는다. * 2. 다른 섬과 이어지는 가장 가까운 장소를 찾고, 거리를 저장한다. * 3. 그 거리들 간의 최소값을 출력한다. */#include #include #include #include #include using namespace std;int dx[4] = {0, 0, -1, 1};int dy[4]..
문제 링크[13549 숨바꼭질 3]접근 및 해결일반 bfs 방법으로 풀려고 했으나 계속 틀려서 질문 게시판을 찾아 보았다.이 문제에서는 간선의 가중치가 다르기 때문에, 먼저 도착했더라도 그 경로가 최소임을 보장할 수 없다.초기 코드 - 실패#include #include using namespace std;const int MAX = 100000 + 1;int board[MAX];int N, K;int dx[2] = {-1, 1};int main(){ cin >> N >> K; queue q; q.push(N); board[N] = 1; while (!q.empty()) { int cur = q.front(); q.pop(); if (..
문제 링크[1600 말이 되고픈 원숭이]접근[벽 부수고 이동하기]와 문제가 비슷하다고 생각했다. 따라서 visited 배열로 3차원 배열을 선언하고, 원숭이가 능력을 쓸 때마다 visited 배열의 ‘면’을 증가시키는 방법으로 접근했다.어려웠던 점가로, 세로, 행, 열이 어려웠다………………………헷갈렸다…………………………………………원소 접근 방식가로 - 열세로 - 행가로, 세로일 땐 map[y][x] 방식으로 접근해서 풀어야 한다. (꼭 그렇다는게 아니라 그냥 저의 다짐입니다 ..)코드#include #include #include using namespace std;#define W_MAX 201 // 가로 (열)#define H_MAX 201 // 세로 (행)#define K_MAX 31 ..
