탐색 (13) 썸네일형 리스트형 [Baekjoon]2589.보물섬 2589.보물섬 http://www.acmicpc.net/problem/2589 맵이 주어졌을때 두 지점의 최단거리 중 최댓값을 구하는 문제이다. 노드 간 최단 경로를 찾는 문제이므로 bfs를 사용했다. 맵을 순회하며 땅인 지점에서 bfs를 수행. dist배열에 거리 저장. dist배열에서 최댓값을 찾고, 1로 돌아가서 반복. dist배열은 2차원 배열로 bfs를 시작한 지점으로부터 해당 인덱스까지의 거리를 저장한다. 시작 지점에 따라 최단거리가 다르기 때문에 bfs가 끝나면 초기화해주고 다른 육지 지점으로 가서 다시 bfs를 수행한다. 육지가 위 그림처럼 생겼을때 처럼 1에서 bfs를 수행하면 가장 멀리 떨어진 지점까지 거리는 4이다. 하지만 와 같은 경우가 최댓값을 가진다. 이 점을 잘 생각하여 di.. [Baekjoon]2573.빙산 2573.빙산 http://www.acmicpc.net/problem/2573 dfs로 푸는 문제였는데 문제의 조건 하나를 생각하지 못해서 계속 시간초과가 났다. 문제를 꼼꼼히 읽고 이해하는 연습이 더 필요할 것 같다. 접근은 다음과 같다. 빙산을 녹인다. dfs로 빙산의 개수를 카운트한다. 카운트가 2이상이면 종료하고 아니면 1로 돌아가서 반복한다. 빙산을 녹이는 melting메소드를 짜면 나머지는 일반적인 탐색문제와 동일하다. 먼저 getAdjSea메소드로 각 칸이 인접한 0의 개수(바다와 인접한 면)를 세서 melt배열에 따로 저장한다. 그 다음 원래 배열 map에서 배열melt에 저장된 값을 빼주고 만약에 그 값이 0보다 작으면 0으로 저장한다. 이후에 map을 순회하며 빙산을 만나면 dfs를 실.. [Baekjoon]2468.안전 영역 2468.안전 영역 http://www.acmicpc.net/problem/2468 연구소, 단지번호 붙이기 등 탐색 문제와 비슷한 방법으로 풀 수 있는 문제였다. 강수량 1증가. 탐색으로 안전영역 카운트. 최댓값이면 갱신, 아니면 1로 돌아가서 반복. 탐색은 dfs를 이용했고 explore메소드는 맵을 순회하며 dfs를 할지 말지 결정하는 메소드이다. 단지 번호 붙이기에서도 같은 방법을 사용했다. 다른 문제풀이와 다른 점은 flood메소드에 있다. 먼저 모든 지역이 물에 잠길 때까지만 함수를 실행하기위해 주어진 맵의 최고점을 max에 저장해놓고 while문을 통해 강수량이 max보다 작을 동안에만 실행했다. 또한 강수량이 증가할때마다 탐색을 다시 진행하기위해 visited배열을 초기화했다. privat.. [Baekjoon]14502.연구소 14502.연구소 http://www.acmicpc.net/problem/14502 삼성 SW역량테스트 기출문제였다고 한다. 완전탐색+dfs or bfs 의 문제라고 생각했다. 먼저 구조를 생각해보면 벽을 3개 세운다. 바이러스를 퍼뜨린다. 안전영역의 개수를 센다. 최댓값인지 확인하고 아니면 1로 돌아가서 반복. 최댓값이면 리턴. 여기서 벽을 3개 세우는 것이 문제였다. map에서 0인 부분에서 3개를 골라서 벽을 세워야 하므로 조합개념을 사용해야 했다. 2차원 배열에서 모든 좌표를 다 해보는 방법을 몰라서 찾아본 결과 다음과 같은 방법으로 모든 좌표를 탐색할 수 있었다. N*M 2차원 배열이 주어졌을때 N*M개 중에서 3개를 뽑는다고 생각하면 된다. i를 0~N*M 까지 증가시키면서 (i/M, i%M).. [SWEA]1226.미로 탐색 문제 중에 기본적인 문제다. bfs, dfs 둘 다 가능해보였는데 bfs로 풀었다. 좌표를 저장하기 위해 Point 클래스를 만들어서 사용했지만 다른 사람들 풀이에서는 그냥 2차원배열 인덱스를 이용했다. 탐색문제에서는 좌표나 노드 클래스를 만들어서 푸는 버릇이 있어서 이렇게 풀었다. 어떤게 더 좋은 방법인지는 모르겠다. q에 다음에 방문할 점을 넣으면서 반복문을 돌렸다. 크게 세가지 조건에 따라 반복문을 수행하도록 했다. 다음에 방문할 점이 도착지이면 반복문 종료 map의 범위를 벗어나면 pass. 이미 방문한 점이거나 벽이면 pass. 탐색문제에서 대부분 다루는 조건이기 때문에 특별히 어려운 건 없었다. 1227.미로2 문제도 있는데 단순히 map의 크기만 100*100으로 늘어난 문제였다. 이전 1 2 다음
