본문 바로가기

그래프 탐색20

[자바] 백준 11559 - Puyo Puyo (java) 문제 : boj11559 필요 알고리즘 개념 BFS (너비 우선 탐색) 등의 그래프탐색, 시뮬레이션 연결된 뿌요들을 파악하기 위해 BFS, DFS와 같은 그래프 탐색이 필요하다. 그 외에는 그냥 제시된대로 시뮬레이션을 돌려주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 그래프 탐색을 모른다면 BFS 글을 봐보자. 시뮬레이션으로 생각해본다면 다음의 과정을 진행하면 된다. 1. 연결된 4개이상의 뿌요들을 없앤다. 없앨.. 2023. 1. 16.
[쇼미더코드 3회] 백준 27211 - 도넛 행성 (자바 java) 문제 : boj27211 필요 알고리즘 개념 BFS (너비 우선 탐색) 약~간 응용된 BFS 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 BFS를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS 글'을 참고해보자. 사실 위 글을 이해했다면 그냥 BFS와 다를바가 없다. 그냥 NxM 사이즈를 넘어갔을 때, 반대편으로 이동만 가능하도록 해두면 된다. 입력으로 주어진 지도 정보를 가로세로.. 2023. 1. 15.
[자바] 백준 1981 - 배열에서 이동 (java) 문제 : boj1981 필요 알고리즘 개념 투 포인터, 이분 탐색 투 포인터 혹은 이분 탐색을 섞은 그래프 탐색 문제이다. 일단 태그는 이분 탐색이긴 한데, 난 투 포인터로 풀었다. 그래프 탐색(BFS, DFS) 투포인터 혹은 이분 탐색으로 제한된 범위 내에서 시작점부터 끝 점까지 탐색이 가능한지 확인해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이하 풀이는 투 포인터를 사용한 풀이이다. 태그를 보니 대부분 이분.. 2022. 12. 13.
[자바] 백준 2842 - 집배원 한상덕 (java) 문제 : boj2842 필요 알고리즘 개념 투 포인터, 그래프 탐색 당연히 bfs나 dfs 문제처럼 생겼는데, dfs나 bfs는 그저 탐색을 위해 거들뿐인 문제이다. 투 포인터 혹은 이분탐색 등을 사용해 범위를 조정해나가는 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 혹시 BFS를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고하자. 투 포인터는 써둔게 없지만.. 2022. 12. 12.
[자바] 백준 17071 - 숨바꼭질 5 (java) 문제 : boj17071 필요 알고리즘 개념 그래프, BFS (너비 우선 탐색) 결론적으로 보면 그냥 BFS 문제이다. 다만 아이디어가 좀 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 생각 과정 및 풀이 이 문제의 경우 상당히 많이 잘못 생각했고, 결론적으로 proof by AC (정답 맞췄으니 증명됬다!) 느낌으로 풀었다 ㅋㅋ. 그러니 풀이를 생각한 과정을 적어보겠다. 정답 코드만 볼꺼면 맨 아래의 코드만 보면 될 .. 2022. 11. 29.
[자바] 백준 19542 - 전단지 돌리기 (java) 문제 : boj19542 필요 알고리즘 개념 깊이 우선 탐색 (dfs), 트리 트리를 dfs로 적절한 방식으로 탐색하는 문제이다. 기본적으로 dfs에 대한 이해가 필요하다. 트리에 대한 이해도 있으면 생각하기 더 좋다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 요즘 바빠서 브론즈문제로 스트릭만 유지하고 있었다. 현재 405일이라 깨기는 너무 아깝다 ㅋㅋ 이제 좀 바쁜게 풀려서 다시 문제들좀 풀어보려니 오랜만이라 그런지 .. 2022. 11. 3.
[자바] 백준 25601 - 자바의 형변환 (java) 문제 : boj25601 필요 알고리즘 개념 그래프 탐색 (bfs, dfs) 그래프 탐색을 할 수 있어야 한다. bfs, dfs 등 해시를 사용한 집합과 맵 String에 대한 간선 표현을 위해 HashMap 등의 자료구조를 사용할 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이게 뭔가 복잡해보일 수 있는데, 결국 그냥 그래프 정점과 간선이 주어지고 특정 지점에서 다른 지점으로 그래프 탐색이 가능하냐고 묻.. 2022. 10. 7.
[자바] 백준 1682 - 돌리기 (boj java) 문제 : boj1682 내 경우 String을 기준으로 한 bfs로 풀었다. 우선 수열이 '1,2,3,4,5,6,7,8' 이라고 한다면 이걸 String으로 "12348765"로 변경한다. 즉 수열의 순서와 관계없이 그냥 내가 알아보기 편하게 배열에 나타나는 순서대로 String으로 만들었다. 어떻게 하든 상관은 없다. 마찬가지로 입력이 '6 4 2 8 1 3 5 7'일 경우 String으로는 "64287531"로 표현했다. 이런식으로 입력으로 들어온 값을 String으로 변환한걸 GOAL, 시작 수열을 String으로 변환한 "12348765"를 START라고 해보자. 그럼 이제 A, B, C, D의 4가지 변환 과정을 거쳐 START에서 GOAL로 최소 몇 번 만에 변환되는지 알 수 있으면 된다. 이.. 2022. 7. 23.
[자바] 백준 18818 - Iguana Instructions (boj java) 문제 : boj18818 bfs로 진행하되, 거리가 증가되는 기준이 한 방향으로 일직선으로 장애물을 만나기 전까지 모두가 동일한 거리를 가진다.그리고, 한 방향으로 일직선으로 진행하면서 만난 모든 지점을 큐에 추가하면서 풀어주면 된다. 예를들어 예제 입력 2를 봐보자. 5 ..... .###. ..... .#### ..... 우선 시작점에서 bfs를 진행한 결과에 따른 각 지점의 거리는 다음과 같다. 그리고 현재 거리가 '1'인 지점은 모두 큐에 추가된 상태이다. 맨 윗줄만 봤을 때, 2,3,4번째 칸들은 더이상 진행할 곳이 없으므로 그대로 무시된다. 맨 윗줄 5번째칸에서 진행한 결과는 다음과 같을 것이다. 다음으로 좌측줄 정중앙에서 진행한 결과는 다음과 같다. 마지막으로 맨 아래줄 좌측에서 진행한 결과.. 2022. 6. 8.
[자바] 백준 21941 - 문자열 제거 (boj java) 문제 : boj21941 기존에 그리디로 생각해서 풀었었는데, 재채점이 되어 틀려있었다. 기존 틀린 풀이는 여기에 있다. 다시 풀어서 작성한다. 문자열 s를 각 인덱스(이하 idx)를 정점으로 하는 가중치를 가지는 방향 그래프로 바꿔서 생각해보자. 이 때, '문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.' 라는 부분은 idx -> idx+1 로 가는 가중치 1의 간선으로 바꿀 것이다. 그리고 문자열 Ai와 그에 따른 가중치는 예를들어 s가 "abcd"이고, A1이 bc이고 가중치가 3이라고 한다면 idx=1 -> idx=3으로 향하는 가중치 3의 간선이라고 할 수 있다. 예제 입력 1을 봐보자. abcxyzxabc 2 abc 10 xyz 5 위에서 말한 그래프로 그려보면 다음과 같다. .. 2022. 5. 31.

티스토리툴바