728x90 반응형 JAVA13 프로그래머스 Level 3 – 여행경로(Java, DFS 백트래킹) 풀이 ✈️ 프로그래머스 Level 3 – 여행경로(Java, DFS 백트래킹) 풀이오늘은 프로그래머스에서 정말 자주 등장하는 그래프/백트래킹 문제,바로 “여행경로” 문제를 정리해봤다.이 문제의 핵심은 아주 단순하다.주어진 항공권들을 모두 사용해서 만들 수 있는 경로 중사전순으로 가장 앞서는 경로를 찾는 것.그래서 DFS + 백트래킹을 이용해"항공권을 사용했다가 다시 되돌리기" 작업을 하면서모든 경우의 수를 탐색한다.📌 문제 핵심 포인트✔️ 1. 항상 "ICN"에서 출발문제에서 출발점이 고정되어 있다.✔️ 2. 티켓을 사전순으로 정렬해야 함왜?→ DFS 진행 중 여러 경로가 생기는데,사전순으로 정렬해두면 가장 먼저 완성되는 경로가 곧 정답이기 때문이다.✔️ 3. 모든 티켓을 사용했을 때가 종료 조건티켓 개수가.. 2025. 11. 18. 프로그래머스 Level 3 – 아이템 줍기(Java, BFS + 테두리 따라가기) 🎒 프로그래머스 Level 3 – 아이템 줍기(Java, BFS + 테두리 따라가기)이번 문제는 프로그래머스에서 난이도와 구현 난이도가 꽤 있는 편인 ‘아이템 줍기’ 문제다.직사각형 여러 개가 겹쳐 있는 지도 위에서 테두리만 따라 이동하여 캐릭터가 아이템까지 최단 거리로 도달하는 경로 길이를 구하는 문제.이 문제의 핵심은 단 하나다.❗ 직사각형 내부로 들어가면 안 되고,❗ 테두리만 따라 이동해야 하며,❗ 겹침/교차 때문에 지도 해상도를 2배로 늘려서 정밀도를 확보해야 한다.그렇다.기본 BFS처럼 보이지만, 실제로는 “테두리 구분을 위해 좌표를 2배 확대하는” 아이디어가 있어야 제대로 풀 수 있다.📌 문제 핵심 아이디어✔ 1. 좌표를 2배로 키워서 정밀도 확보겹치는 사각형 영역이 많기 때문에 실제 좌표.. 2025. 11. 18. 프로그래머스 Level 3 – 단어 변환(Java, BFS) 🔤 프로그래머스 Level 3 – 단어 변환(Java, BFS)이번에 풀어본 문제는 단어(begin → target) 변환 과정에서 최소 단계 수를 구하는 BFS 문제이다.문제 조건이 흥미로운데, 한 번에 단 하나의 알파벳만 바꿀 수 있고,그렇게 바꾼 단어가 반드시 words 리스트 안에 있어야 한다.이 조건 때문에“그래프 탐색 문제처럼 보이지만, 사실 문자열을 노드로 취급하는 BFS 문제”로 해석하면 훨씬 쉽게 풀린다.📌 문제 핵심 요약시작 단어: begin목표 단어: target사용할 수 있는 단어 리스트: words[]한 번에 1글자만 변화 가능words에 없는 단어로는 이동 불가begin → target 까지 도달하는 최소 단계 수 구하기결국 begin을 시작점으로 두고 words 안의 단어들.. 2025. 11. 18. 프로그래머스 Level 2 – 게임 맵 최단거리(Java, BFS) 🎮 프로그래머스 Level 2 – 게임 맵 최단거리(Java, BFS)이번에 풀어본 문제는 프로그래머스에서 BFS 대표 문제로 유명한**“게임 맵 최단거리”**다.시작점(0,0)에서 도착점(n-1,m-1)까지 최소 몇 번 만에 갈 수 있는지를 구하는 문제이며,정답은 BFS로 간단하게 해결할 수 있다.📌 문제 요약maps[i][j] == 1 → 이동 가능maps[i][j] == 0 → 벽이라 이동 불가(0,0)에서 출발해 (n-1,m-1)까지 가는 데 필요한 최소 이동 거리를 반환갈 수 없다면 -1 반환즉, 미로 최단거리 문제이므로 BFS가 정석이다.🧠 핵심 아이디어✔ 1. BFS는 최단거리 찾기에 최적화된 알고리즘한 번 방문한 칸은 그때의 이동 거리가 최단 거리다.✔ 2. maps 배열을 그대로 ‘.. 2025. 11. 18. 이전 1 2 3 4 다음 728x90 반응형