BFS

[백준, Java] 14226번 : 이모티콘

🔗 문제 링크 https://www.acmicpc.net/problem/14226 😮 문제 해결 방법 BFS를 이용한 완전 탐색 방식으로 문제를 해결했다. 최초의 경우에는 화면에만 이모티콘이 있으므로 큐에 넣고 시작한다. 현재 시간에만 할 수 있는 행동을 구분하기 위해서 큐의 사이즈만큼만 현재 초에는 반복을 돌게 한다. 각각의 행동은 아래와 같은 조건에 따라서 할지 말지 구분할 수 있다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 보내려는 이모티콘 개수보다 화면에 있는 이모티콘의 개수가 더 적은 경우에 이모티콘을 복사하는 것이 의미있다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 보내려는 이모티콘 개수보다 화면에 있는 이모티콘의 개수가 더 적은 경우에 이모티콘을 클립보드로 가..

[백준, Java] 1039번 : 교환

🔗 문제 링크 https://www.acmicpc.net/problem/1039 😮 문제 해결 방법 주어진 숫자 M에 대해서 자릿수 교환이 K번 일어났을 때 나올 수 있는 최대값을 구하는 문제이다. 자릿수 i보다 자릿수 j가 더 커야하는 제한 조건이 있기 때문에 교환할 수 있는 자릿수의 순서쌍을 모두 구한다. 모두 구한 순서쌍과 함께 초기에 주어진 M 값과 K = 0인 상태로 큐에 넣어준다. 매 턴 마다 존재할 수 있는 값을 순서쌍을 이용해 구한다. 큐의 사이즈만큼 반복한다. 순서쌍을 이용해 자릿수 교환이 이뤄졌을 때 값을 체크한다. 이미 현재 턴에 교환한 숫자가 나왔거나 0으로 시작하는 경우의 값은 큐에 넣지 않는다. 만약 턴을 모두 사용한 경우에는 Set에다가 넣어주고 큐에는 넣지 않는다. 이외의 경..

[백준, Java] 18352번 : 특정 거리의 도시 찾기

🔗 문제 링크 https://www.acmicpc.net/problem/18352 😮 문제 해결 방법 문제의 조건에서 최대 300,000개의 도시가 입력으로 주어질 수 있다고 명시했기 때문에, 인접행렬 방식이 아닌 인접 리스트 방식으로 해결해야한다. 시작 도시부터 도달할 수 있는 모든 도시에 대해 최단거리를 구하는 알고리즘은 “다익스트라"를 사용할 수 있다. 물론, 해당 문제에서도 다익스트라 알고리즘을 사용할 수 있지만, 각 도시간 거리가 1로 고정이 되어있기 때문에 BFS를 이용해서도 문제를 해결할 수 있다. 출발 도시를 시작으로 BFS를 구현한다. 연결된 도시 중 방문하지 않고, 현재 도시에서 거리에 +1 한 값보다 연결된 도시 거리가 멀다면 최단 거리로 갱신한다. 시작 도시로 부터 도달할 수 있는 ..

[백준, Java] 16928번 : 뱀과 사다리 게임

🔗 문제 링크 https://www.acmicpc.net/problem/16928 😮 문제 해결 방법 주사위를 조작할 수 있다고 문제에서 제시했기 때문에 매 위치마다 1~6번까지의 주사위를 던진 후 위치를 담은 Node 객체에 다음 위치와 다음 거리(주사위 던진 개수)를 넣어 큐에 넣어주었다. 매 주사위 굴린 후의 위치에서는 뱀과 사다리가 있는 칸인지 먼저 확인한다. 뱀과 사다리가 있는 칸인 경우 주사위를 한번 굴린 것으로 뱀과 사다리를 탄 이후의 칸으로 이동이 가능하기 때문에 뱀과 사다리 탄 이후 칸 거리 배열에 현재까지 위치의 주사위 개수 + 1을 한 값을 넣어준다. 뱀과 사다리가 없는 칸인 경우 주사위 굴린 이후의 칸 거리 배열에 현재 까지의 주사위 개수 + 1 한 값을 넣어준다. 현재 큐의 칸이 ..

[백준, Java] 2573번 : 빙산

🔗 문제 링크 https://www.acmicpc.net/problem/2573 😮 문제 해결 방법 빙산을 녹여야 하는지 판단을 하는 배열과 실제로 인접한 바다를 체크한 후 녹은 후의 빙산 상태를 저장하는 배열 두개를 사용해서 해결했다. 빙산 상태를 녹이는 배열은 현재 해의 빙산 배열을 복사한 배열이다. 기존 빙산 배열을 녹은 후 빙산 상태를 저장하는 배열로 사용하기 위해 복사한다. 기존 빙산 배열을 이용해서 빙산이 남아있고, 상하좌우 인접한 부분에 바다가 있는지 판단한다. 이 때, 단 하나로 빙산이 남아있지 않았다면, 빙산이 다 녹을때 까지 두 덩어리 이상으로 빙산이 나눠지지 않았기 때문에 0을 리턴하고 종료한다. 상하좌우 인접한 바다의 개수 만큼 빙산의 크기를 녹여준다. 현재 해의 녹일 수 있는 빙산..