Algorithms/SWEA (3) 썸네일형 리스트형 [SWEA]1953.탈주범 검거 bfs로 푸는 문제였다. 그런데 파이프가 연결되어 있는 지점으로만 이동이 가능하기 때문에 현재지점에서 상하좌우를 확인하여 연결이 된 지점으로만 탐색을 수행해야한다. 현재 지점의 파이프 번호에 따라서 탐색할 수 있는 방향이 정해져 있다. 예를 들면 현재 지점의 파이프번호가 2번이면 어차피 좌우로는 이동할 수 없기 때문에 상하 방향만 탐색하도록 한다. 이처럼 파이프 번호에 따라 탐색할 방향을 for문 안에서 미리 걸러주었다. 문제를 풀 때 한가지 착각을 했다. y좌표가 + 되는 것이 아래로 이동하는 방향이고 - 되는 것이 위로 이동하는 방향인데 이것을 반대로 생각해서 계속 틀렸다. 방향에 주의하자. private static void bfs() { visited[R][C] = true; q.add(new P.. [SWEA]1949.등산로 조성 dfs + 완전탐색으로 풀었다. 처음엔 백준의 벽 부수고 이동하기와 비슷하다고 생각해서 bfs로 접근했지만 가능한 길게 등산로를 만들어야 하기 때문에 dfs로 푸는게 일반적인 풀이라는 것을 알았다. 봉우리들을 찾는다. 봉우리마다 등산로 조성을 해본다. 인접한 곳이 내리막길이 아니면 1씩 깎아보면서(K까지만) 내리막이 되면 탐색을 계속한다. 먼저 맵에서 가장 높은 곳의 높이를 highest에 저장하고 그 지점들을 peak배열에 삽입한다. peak배열에서 봉우리를 하나씩 꺼내서 탐색을 한다. 탐색을 할 때 이전에 지형을 깎는 공사를 했는지 안했는지 여부를 체크하기 위해 flag 변수를 사용한다. 지형을 깎는 공사를 이미 했다면 더 이상 깎는 공사를 할 수 없으므로 현재 지점보다 낮은 지점으로만 탐색을 계속해.. [SWEA]1226.미로 탐색 문제 중에 기본적인 문제다. bfs, dfs 둘 다 가능해보였는데 bfs로 풀었다. 좌표를 저장하기 위해 Point 클래스를 만들어서 사용했지만 다른 사람들 풀이에서는 그냥 2차원배열 인덱스를 이용했다. 탐색문제에서는 좌표나 노드 클래스를 만들어서 푸는 버릇이 있어서 이렇게 풀었다. 어떤게 더 좋은 방법인지는 모르겠다. q에 다음에 방문할 점을 넣으면서 반복문을 돌렸다. 크게 세가지 조건에 따라 반복문을 수행하도록 했다. 다음에 방문할 점이 도착지이면 반복문 종료 map의 범위를 벗어나면 pass. 이미 방문한 점이거나 벽이면 pass. 탐색문제에서 대부분 다루는 조건이기 때문에 특별히 어려운 건 없었다. 1227.미로2 문제도 있는데 단순히 map의 크기만 100*100으로 늘어난 문제였다. 이전 1 다음