[백준] 2206번 벽 부수고 이동하기 (Java)
2206번 벽 부수고 이동하기 1. 문제 분석 0은 이동할 수 있는 칸, 1은 벽이 있어서 이동할 수 없는 칸입니다. (1, 1)에서 시작해서 (N, M)까지 가는데 최단 경로를 구해야 합니다. 이동은 상, 하, 좌, 우로 가능하고, 이때 벽(1)을 최소 한번 부수고 지나갈 수 있습니다. 문제에서 주어진 사항을 보고, BFS로 접근해야겠다는 생각을 했습니다. 방향이 존재하기 때문에 재귀적으로 구현을 했고, 벽을 1번 이상 부순 경우는 더 이상 나아가지 못하도록 막는 방법을 생각했습니다. 계속 틀렸다는 말이 나와서 2차원 배열 visited를 이용하여 문제를 변경해서 풀어봤는데, 이때는 시간 초과가 났습니다. 2. 핵심 아이디어 특정한 지점 (x, y)에 도달하는 데 있어서 벽을 1번 부수고 가는 경우와 ..
[백준] 1931번 회의실 배정 - Java
백준 1931번 회의실 배정 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 📖 문제 그리디 알고리즘의 대표적인 예시 문제라고 해도 될 문제입니다. 그래서 풀이에 대해서 조금 정리해보려고 합니다. 🔎 접근 방법 회의 일정에는 시작 시간과 종료 시간이 존재합니다. 회의 일정은 겹치면 안되고, 최대한 많은 회의를 진행해야 합니다. 위 조건을 생각해봤을 때, 이전 회의 일정의 종료 시간과 겹치지 않아야 하고 이후 일정의 시작 시간과 겹치지 않아야 합니다. 즉, 회의 일정을 종료 시간 기준으로 오름차순 정렬하여 종료 시간이 빠른 일정부터 해결해나가면 정답에 접근할 수 있습니다. 1. 회의 일정을 저장할 수 있는 클래스 선언 후 Co..