Algorithm/BFS & DFS

[백준, 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] 19621번 : 회의실 배정 2

🔗 문제 링크 https://www.acmicpc.net/problem/19621 😮 문제 해결 방법 문제의 제한 조건에서 K 번째 회의는 K-1 , K+1번째 회의와 겹친다고 했기 때문에 K 기준으로 회의를 참석하는 경우 K-1, K+1회의는 참석할 수 없다. 반대로 회의에 참가하지 않는 경우 K-1, K+1 회의는 참가할 수 있다. 따라서, 첫 회의를 기준으로 참가하는 경우와 불참하는 경우로 DFS를 이용한 완전탐색으로 문제를 해결했다. 회의의 최대 개수가25개까지 주어지므로 DFS를 이용한 완전탐색이 가능하다. 첫 번째 회의 기준으로 참가와 불참 경우로 탐색을 진행한다. 첫 번째 회의에 참가하는 경우 2번째 회의는 참가하지 못하기 때문에 3번째 회의에 참가하도록 depth + 2를 해주고 현재 회의..

[백준, Java] 9934번 : 완전 이진 트리

🔗 문제 링크 https://www.acmicpc.net/problem/9934 😮 문제 해결 방법 상근이가 도시를 방문한 조건을 살펴보면 가장 왼쪽에 있는 도시까지 방문한 후 그 부모를 방문 한 뒤 다시 오른쪽을 탐색한다. 즉, inorder 중위 순회 방식과 동일하다. 상근이가 방문한 도시의 트리 모양을 표현해줘야 하는 것이 목적이므로, 노드 번호가 1, 2, 3 순차적으로 증가하는 완전 이진 트리를 새로 만들어줬다. 새로 만든 트리를 이용해 중위 순회를 한 후 방문한 도시들을 스택에 저장한다. 입력으로 받은 도시와 스택에 저장한 도시가 동일한 순서이기 때문에 입력으로 받은 도시와 스택에 저장한 도시를 하나의 클래스로 매핑해준 뒤 새로 만든 트리의 모양대로 만들어준다. 새로 만든 트리는 노드 번호가 ..

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

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