Live Today

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 💡 최단 경로 알고리즘 -> 다익스트라 ✔️ 문제 리뷰 문제를 읽자마자 출발지에서 도착지로 가는 최단 경로 문제라는 것을 알아차렸다. "농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다." -> 헛간 1이 출발지이고 헛간 N이 도착지이다. "농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요?" -> 헛간 1에서 헛간 N으로 가는 최..

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 💡 BFS + 그래프 탐색 ✔️ 문제 리뷰 계속 12%에서 시간 초과가 발생했다. 문제는 불이 퍼지는 과정에서 board 2차원 배열을 매번 for문으로 탐색해서 시간 초과가 발생한 것이었다. 그래서 이 부분을 Queue로 관리해주니 해결됐다! ✔️ 문제 풀이 불이 먼저 1초에 한 칸씩 퍼진다. 그 다음, 상근이가 이동 가능한 칸으로 이동한다. 상근이가 이동 중, 범위 밖으로 벗어나서 탈출하는 경우와 다음 칸..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 💡 DFS + DP ✔️ 문제 리뷰 처음에는 DFS를 사용해서 visited 2차원 배열로 방문 체크를 하여 풀었다. 하지만 이 문제는 visited 대신 dp 2차원 배열을 사용해 기존에 방문하지 않았던 칸만 탐색해야 하는 문제였다. 단순 DFS로만 풀면 시간초과가 발생한다. ✔️ 문제 풀이 초기 dp 2차원 배열을 모두 -1로 초기화한다. (0,0)부터 DFS를 시작하여 dp[x][y] 값이 -1인..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 💡 부분 집합 + bfs ✔️ 문제 풀이 부분 집합으로 지역을 2가지로 나눈다. 지역이 2가지로 나뉘어졌다면, 각 지역이 서로 연결되어 있는지 bfs를 통해 확인한다. 두 지역의 인구 차이를 구한다. result에 가장 최솟값으로 갱신시킨다. ✅ 정답 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 💡 구현 + 시뮬레이션 ! ✔️ 문제 리뷰 한 번에 통과했다. 50분 걸려서 풀었다 ! ✔️ 문제 풀이 현재 칸이 청소되지 않은 칸인 경우, 청소한다. 현재 칸의 주변 4칸 중, 청소되지 않은 빈 칸이 없는 경우, 바라보는 방향을 유지하며 한 칸 후진한다. 1번으로 돌아간다. 이동한 칸이 벽인 경우 로봇 청소기 작동을 멈춘다. 현재 칸의 주변 4칸..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 💡 브루트포스 → dfs ✔️ 한 번에 통과 못 한 이유 cctv 4번의 감시 구역 방향 설정을 제대로 못했다. 4번의 {0,1,3},{0,1,2} 이 두개를 빼먹고 풀어서 틀렸다. static int[][][] move = { {{0}}, {{0},{1},{2},{3}},// 1번 {{0,1},{2,3}}, // 2번 {{0,3},{1,3},{1,2},{2,0}}, // 3번 {{0,..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net ✔️ 한 번에 통과 못 한 이유 이 문제는 시간 제한이 0.3초라 단순 구현으로는 풀면 통과하기 어려워서 자료구조를 잘 선택해서 풀어야 했다. 처음에 풀었던 코드는 나무를 저장하기 위해 HashMap과 ArrayList로 구현을 했다. 하지만, 굳이 모든 나무에 대한 데이터를 한 번에 가지고 관리하려다 보니 필요하지 않은 자료구조들을 썼던 것 같다. 그래서 나무를 관리하는 자료구조..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 💡 그냥 구현 + 시뮬레이션 ✔️ 한 번에 통과 못 한 이유 상어 이동하는 함수에서 한 칸에 2마리 이상의 상어가 모였을 경우, 가장 큰 상어만 남기고 나머지 상어들은 sharkList에서 삭제해야 한다. 여기서 sharkList.removeAll(removeList); 를 쓰면 한 번에 removeList에 있는 sharkList의 인덱스에 해당하는 데이터가 삭제될 줄 알았는..

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 💡 중복순열 + 백트래킹 + 완전탐색 ✔️ 한 번에 해결하지 못한 이유 11%에서 틀려서 조금 짜증이 났던 문제 ㅎ--ㅎ 말의 방문체크 부분 때문에 틀렸던 것이었다. "말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다." 이 조건을 고려해야 해서 각 말의 위치 확인이 필요했다. 윷놀이 판에서 16,22,24,26,28,30의 숫자들은 숫자는 같지만 위치가 서로 다른 곳에 있어서 이..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 💡 조합 + 시뮬레이션 + 완전 탐색 + bfs ✔️ 문제 풀이 궁수 3명 배치 → 조합 조합으로 궁수 3명을 배치할 때마다 기존 board 배열을 copy해서 풀어야 함. 각 궁수 위치에서 거리가 D이하이면서 가장 가까운 적 제거 여러 명이면, 가장 왼쪽에 있는 적 제거 result가 최대가 되려면, 각 궁수마다 서로 다른 표적을 제거해야 함. ✅ 정답 코드 import java.io.BufferedRea..