728x90 반응형 BFS26 프로그래머스 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. 프로그래머스 Level 3 – 네트워크(Java, BFS) 🌐 프로그래머스 Level 3 – 네트워크(Java, BFS)이번에 풀어본 문제는 프로그래머스의 대표적인 그래프 탐색 문제인 **“네트워크”**다.회사 컴퓨터들이 서로 연결되어 있을 때, 총 몇 개의 네트워크(= 연결된 그룹)이 존재하는지 찾는 문제다.문제 구조가 전형적인 그래프의 연결 요소 개수 찾기(Connected Components) 라서DFS 또는 BFS 아무거나 사용해도 되지만, 나는 BFS 버전으로 풀었다.📌 문제 요약컴퓨터 개수: n연결 관계: computers[i][j] == 1이면 i와 j는 연결됨서로 이어진 컴퓨터끼리는 하나의 네트워크네트워크가 총 몇 개인지 반환하는 문제즉,방문하지 않은 노드 하나를 발견 → 그 노드를 기준으로 BFS/DFS 돌림 → 연결된 모든 노드를 방문 처리.. 2025. 11. 18. 이전 1 2 3 4 ··· 7 다음 728x90 반응형