SY DevLog

9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net DFS와 트라이 알고리즘을 통해 문제를 해결하였다. 게임 사전에 등재된 단어들을 트라이에 넣는다. 각 보드마다 DFS방식으로 접근하면서 여태까지 지나온 알파벳들로 이루어진 단어가 트라이에 포함되어 있는지를 확인한다. 문제에서 같은 단어를 여러 번 찾은 경우는 하나로 간주한다고 했으므로 중복을 피하기 위해 찾은 단어를 HashSet에 넣어주었다. 기존의 트라이의 contains() 메서드는 true 혹은 false를 반환하였다.특정 단어에 트라이..

2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 비트마스크를 이용한 동적 프로그래밍 + dfs 방법으로 풀 수 있는 문제이다. 아래는 문제 예제의 도시와 경로를 나타낸 것이다. dp 2차원 배열을 생성한다. 첫번째 인덱스는 현재 위치한 도시, 두번째 인덱스는 여태까지 방문한 도시정보를 비트마스크로 표현한다. dp[1][0001(2)] : 현재 위치한 곳은 1번 도시이고, 여태까지 방문한 도시는 1번 도시일 때, 전체 도시를 순회하기 위해 남아있는 최소비용 dp[2][001..

1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 처음에는 문제를 잘못 읽어서 '단순하다 = 한 번 방문한곳을 또 방문한다'라고 이해하는 바람에 계속 답이 안나왔다. 문제를 올바르게 읽는 것의 중요성을 다시 한번 실감했다... 문제 잘못 읽었더니 30분 넘게 소비해버렸다.. 이 문제는 dfs방식으로 visited배열을 사용하여 한 번 방문한 곳을 방문하지 않으면서, 총 N번 이동하면 된다. visited배열은 로봇이 최대 14번 이동이 가능하므로 (15, 15)위치에서 로봇이 출발한다고 할 때, 로봇이 움직..

10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 어느 한 도시에서 출발하여 모든 도시를 거친 후, 처음으로 돌아오는 문제이다. 여기서 알아야 할 사실은 어느 도시에서 출발하든 가장 적게 드는 비용은 동일하다는 것이다. 따라서 아무나 한 곳을 시작도시로 정해서 dfs를 사용하여 시작한 곳으로 돌아오면 된다. 모든 도시를 한 번씩만 방문해야하므로 visited 배열을 이용하여 방문 여부를 표시한다. 그런데 문제를 풀면서 한가지 헷갈렸던 점이 있다. 처음 시작한 도시는 이..

그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) 이번에는 BFS에 대해서 다뤄볼 것이다. DFS(Depth First Search) - 깊이 우선 탐색 그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) DFS 는 이름 그대로 깊이를 우선시 하여 탐색하는 방법이다. '한 우물만 판다' 라는 느낌처럼 한 길만 계속 깊이.. lotuslee.tistory.com BFS는 너비 우선 탐색으로 특정 노드와 연결된 모든 노드들을 우선적으로 탐색한 뒤, 그 중에 하나를 선택하여 또 다시 그와 연결된 모든 노드들을 탐색하는 방식으로 진행된다. 하나의 경로만을 깊..

그래프 탐색에는 두 가지 방법이 있다. DFS(Depth First Search) BFS(Breadth First Search) DFS 는 이름 그대로 깊이를 우선시 하여 탐색하는 방법이다. '한 우물만 판다' 라는 느낌처럼 한 길만 계속 깊이 파고드는 방식이다. 반면에 BFS 는 넓이를 우선시한다. 특정 노드와 연결된 모든 노드를 한번씩 거친 다음에 다음 노드로 이동하는 방식이다. 예를 들어, 다음과 같은 그래프가 있고 1번부터 탐색을 시작한다고 할 때 왼쪽과 같은 탐색 방법을 DFS, 오른쪽과 같은 탐색 방법을 BFS라고 할 수 있다. DFS : 1 -> 2 -> 4 -> 7 -> 6 -> 3 -> 5 BFS : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 위의 DFS 방식에서 처음에 꼭..