Hello Ocean! 🌼

문제 https://www.acmicpc.net/problem/1525 풀이 BFS를 이용해서 풀었다. 그리고 구조체를 만들어, 큐에 구조체를 넣는 방식으로 BFS를 구현했다. 첫 번째 시도 방문체크를 876543211 크기의 배열 이용 구조체 안에 int 3개(r, c, count), 3x3 vector 한 개 → 메모리 초과 ! 두 번째 시도 구조체에 너무 많은 것들이 들어있는게 문제인가 싶어서, 구조체안에 int 1개, string 1개만 넣도록 했다. → 메모리 초과 ! 최종 시도 방문 체크를 string set을 이용해서 했다. 876543211크기의 visited 배열을 만든 것 자체가 메모리 초과의 원인인 것 같았다. 코드 #include #include #include #include #i..

문제 https://www.acmicpc.net/problem/2146 각각의 섬(육지 덩어리?)에서 다른 섬 까지 갈 수 있는 모든 경우의 수 중에 최단 경로를 구하는 문제이다! 풀이 DFS와 BFS를 모두 이용했다. 먼저, 각 섬들의 번호를 구분하기 위해 DFS를 돌렸다. 그 후에 BFS를 돌려서 어떤 섬에서 또 다른 섬까지 갈 수 있는 모든 경우의 수를 구한 후에, 그 중에 최솟값을 출력했다. 맵의 크기(n)이 100이하이기 때문에 input이 작아서 시간초과 걱정 없이 풀었다. 코드 #include #include #include using namespace std; #define LAND 1 #define SEA 0 int dr[4] = { -1,1,0,0 }; int dc[4] = { 0,0,..

문제 https://www.acmicpc.net/problem/2589 육지와 바다로 이루어진 nxm 맵에서 육지에서 시작해서, 바다를 거치지 않고 갈 수 있는 가장 먼 육지까지의 최단경로를 구하는 문제이다. 풀이 BFS를 이용해서 풀었다! 또한, 모든 육지가 시작점이 될 수 있기 때문에 완전탐색이기도 하다. 모든 육지에서 BFS를 돌려서, 다른 육지까지의 최단경로를 모두 구해서 그 중에 최댓값을 출력했다. 코드 #include #include using namespace std; int dr[4] = { -1,1,0,0 }; int dc[4] = { 0,0,-1,1 }; int map[52][52] = { 0, }; int cache[52][52] = { 0, }; int max_dist = 0; vo..

문제 www.acmicpc.net/problem/1707 풀이 처음에는, 벡터 두개를 만들어서 각 그룹에 노드들을 채워나가는 형식으로 했는데 문제점이 있었다. 그래프가 꼭 두 그룹으로 나뉘지 않는다는 것이었다. 아래 그림의 case2와 같이 독립적인 여러개의 그룹으로 나뉠 수 있었다. 그래서 얌전하게 일반적인 그래프 풀이 방식을 이용하였다. BFS로 그래프 탐색 후에, 해당 그래프가 이분그래프인지 확인하는 과정을 거쳤다. 간선을 입력받을 때, v1 -> v2만 저장해서 틀렸습니다가 나왔다. 무방향그래프이기 때문에, v2 -> v1도 저장해야한다! 그리고 BFS를 한 번만 돌리는 것이 아니라, 모든 노드를 방문할 때 까지 여러번 돌려야했다. 코드 #include #include #include using ..

문제 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 소요시간 : 2시간 BFS를 이용해서 풀었다. 구조체를 만들어서 큐에 넣었다. 방문여부를 검사할 때, 해당 노드를 방문하기 전에 벽을 부신적이 있는지 없는지를 구별해서 검사했다. 코드 /* 벽 부수고 이동하기 */ #include #include #include #include using namespace std; int N, M; bool map[1001][1001]; bo..

문제 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 조건이 매우! 많은 문제였다. BFS를 통해서 풀어야 한다는건 알았지만, 계속 오답이 나와서 다른 분들의 풀이를 참고했다. yulme.tistory.com/92 rile1036.tistory.com/90 1. 우선순위 큐 사용 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 ..