149ms 빡구현 BFS 문자에 따라 명령어를 실행시켰을 때, 프로그램 종료 문자인 @ 까지 도달할 수 있는가 없는가에 대해 확인하는 문제이다. 이 문제에서 중요하게 고려해야 할 점은 ? 문자는 4방향 중 어느 방향으로 갈 것인가 프로그램이 종료하지 않는 케이스면 어떻게 종료하지 않은 것을 판단할 것인가 두 가지만 신경쓴다면 복잡하지만 빡구현으로 해결할 수 있다. ? 문자를 만났을 때, 각각의 방향에 따라 경우의 수를 따져야하므로 BFS로 구현하였다. 또한 프로그램이 종료되지 않는 케이스를 판단하기 위해 (행, 열, 방향, 메모리)의 방문체크를 해주는 4차원 배열이 필요하다. (x,y)좌표와 방향, 메모리에 방문체크가 되어있다면 계속 루프를 돌고 있는 것으로 프로그램이 종료할 수 없는 경우이다. 그래서 ..
190ms 구현 BFS 최소의 클릭으로 지뢰를 제외한 모든 칸의 숫자들을 표시하는 문제이다. 핵심은 주변에 지뢰가 없는 칸은 8방향의 칸을 클릭없이 확인할 수 있다는 것이다. 즉, 클릭한 칸을 중심으로 가지가 뻗어나가는 구조로 BFS로 해결하였다. 먼저 주변에 지뢰가 없는 칸을 우선적으로 클릭한 후, 방문처리가 되지 않고 주변에 지뢰가 하나라도 있는 나머지 칸 수를 클릭 수에 더해주면 된다. 1. 각 좌표에서 주변에 지뢰가 몇 개 있는지 체크 ➜ 주변에 지뢰가 몇 개 있는지는 중요한 부분이 아니므로 지뢰가 있으면 1, 지뢰가 없으면 0 으로 저장 2. 주변에 지뢰가 없는 칸(0)을 중심으로 BFS를 실행하며 주변 칸들을 방문처리 해준다. 3. 방문하지 않았으며 주변에 지뢰가 있는 칸(1)은 무조건 한 번..
155ms 간단하게 생각하기 !! 이 문제의 핵심은 입력 중 손님들이 오는 시간은 오름차순으로 주어지지 않는다. 따라서 먼저 Arrays.sort() 를 통해 정렬해준다. 먼저 오는 손님들 부터 탐색하며 손님이 온 시간일 때, 1. 붕어빵을 몇 개 만들 수 있는지 구하기 2. 앞의 손님들의 수(i) 빼줬을 때 0보다 작으면 제공할 붕어빵이 없다는 것 int dessert = (arr[i] / m) * k; if (dessert - i
123ms 구현 부분집합 DFS 이 문제는 가로로 연속된 M개의 칸에서 채취할 수 있는 꿀의 최대 양(C)을 넘지 않으면서 최대한 많은 꿀의 양을 채취할 수 있는 두 구간을 찾아내는 문제이다. 이 문제의 핵심은 두 구간이 겹치면 안된다 → 즉, M개의 칸 중 일부칸만 이용했더라도 M개의 칸 전체와 겹치면 안됨 연속된 M개의 칸을 선택한 후 채취할 꿀 칸을 선택하는 건 연속하지 않아도 된다 (아래그림 참조) 행마다 최대수익을 얻는 경우를 찾은 후, 그 중 최대수익이 가장 큰 행을 찾아 그 값을 결과에 더하고 다시 그 행만 최대수익을 구해준다. (단, 이전에 선택된 칸은 제외) 다시 행마다 최대수익이 가장 큰 행을 찾아 결과에 더해주며 해결하였다. 조건에 맞게 구할 수 있는 조합에서 최대 수익을 얻는 경우 ..
구현 DFS 달마다 1일 이용권 / 1달 이용권 / 3달 이용권 / 1년 이용권을 쓸 때, 가작 적은 비용으로 일년동안 수영장을 이용할 수 있는 경우를 찾아 비용을 출력하는 문제이다. 1년 이용권은 달마다 탐색할 필요가 없어 미리 result 에 1년 이용권 요금을 넣어둔 후, 1일/1달/3달이용권을 달마다 DFS를 통해 탐색해보고 최소비용을 찾아 result와 비교한 후 답을 출력하였다. dfs(m + 1, sum + price[0] * year[m]); dfs(m + 1, sum + price[1]); dfs(m + 3, sum + price[2]); DFS를 이용하면 쉽게 해결할 수 있는 문제였다. #소스코드 import java.io.BufferedReader; import java.io.File..
구현 길이가 K인 마름모 모양의 영역 내에 존재하는 집들이 있을 때, (운영비용) - (집이 지불하는 비용) * (집의 수) 가 양수이면서 집의 수가 최대일 때를 찾으면 된다. K는 1부터 전체 영역을 포함할 수 있는 길이인 N * 2 까지 가능하며 K 길이와 좌표에따라 완전탐색으로 해결할 수 있는 문제이다. 로직은 생각하기 쉬우나 마름모 모양의 영역 내에 집이 존재하는가에 대한 체크하는 과정에서 어려움이 있었다. 마름모의 중심을 기준으로 반지름이 k인 원을 생각해주면 된다. 즉, 중심 좌표와 집의 좌표까지 거리가 k보다 작으면 마름모 영역 내에 존재한다는 것을 의미한다. Math.abs(house[0] - i) + Math.abs(house[1] - j) < k 마름모 시렁 # 소스코드 import j..
121ms BFS 인접행렬 시작 index부터 방향 그래프로 연결된 index로 계속해서 가지처럼 뻗어나가며 마지막의 도달하는 index를 출력하는 문제이다. 마지막에 도달하는 index가 여러 개일 경우 가장 큰 index를 출력한다. 번호index와 도달하는 시간time을 저장할 수 있는 node 클래스를 만들어 BFS를 진행하며 큐가 비어 종료하기 직전 시간과 일치한 시간을 가진 node 중 index가 가장 큰 node를 출력하는 방식으로 구현하였다. 시작값start을 먼저 먼저 큐에 담고 방문처리한 후, 방향그래프인 graph[start][]와 연결된 i를 찾아 방문처리 및 시간을 하나 증가하여 큐에 넣어주며 가지가 끝날 때까지 반복해준다. 큐가 종료하기 직전에 저장한 lastTime과 일치하는..
129ms 구현 DFS 최대한 많은 코어를 전원에 연결할 경우, 필요한 전선 길이의 합의 최소를 구하는 문제이다. 단, 전선끼리 교차할 수 없다. (x,y) 좌표에서의 코어가 (x, 0), (x, n-1), (0, y), (n-1, y) 까지 전선을 설치할 수 있는지, 설치할 수 있는 경우에서 전선의 길이가 최소로 되는 방향으로 설치할 수 있도록 한다. 1. 가장자리가 아닌 코어들의 좌표를 리스트에 저장 2. 코어 리스트를 하나씩 돌며 상하좌우 탐색하며 전선을 설치할 수 있는 방향을 찾은 후 방문처리하며 DFS 탐색 진행 2-1. 방문처리하며 진행하다가 중간에 끊겨 해당 방향으로 전선을 설치할 수 없다면 코어의 좌표까지 다시 되돌아가며 방문처리 해제 3. 전선을 설치할 수 있는 방향이 있다면 전선 길이의..
구현 DFS 가장 높은 봉우리에서 시작하여 가장 긴 등산로를 찾아 길이를 출력하는 문제이다. 이 때, 딱 한 곳을 최대 K 깊이만큼 깎을 수 있다는 옵션이 있다. 가장 높은 봉우리 좌표에서 시작하여 상하좌우 탐색하며 처음으로 이전 봉우리보다 큰 봉우리를 만난 경우, 1 ~ K 깊이로 깎아 이전 봉우리보다 작아지면 이어서 탐색할 수 있도록 한다. 딱 한 곳만 깎을 수 있으므로 한 번 깎았다면 탐색 중 큰 봉우리를 만나도 지나갈 수 없다. 1. 이전 봉우리보다 낮으면 방문처리 후 재귀 2. 이전 봉우리보다 높으면서 한 곳 깎을 수 있는 경우 2-1. 이전 봉우리보다 낮아질 때 까지 깎기 ( 최대 K ) 2-2. 낮아지면 방문처리 및 깎는 공사를 한 번 진행했으므로 flag = true 3. 백트래킹 impo..
10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 92ms DFS BFS 적록색약일 경우의 나눠지는 구역과 적록색약이 아닐 경우 나눠지는 구역의 수를 세는 문제이다. 입력값을 저장할 이차원 배열을 두 개 선언하여 적록색약이 아닌 경우 입력값을 그대로 저장하고 적록색약인 경우에는 'G'값을 'R'값으로 저장하였다. 이중 for문을 돌며 적록색약이 아닌 경우의 dfs, 적록색약인 경우의 dfs 탐색을 통해 주변의 같은 색 좌표들을 모두 방문처리하여 구역을 카운팅하는 방식으로 구현하였다. 좌표의 상하좌우를 탐색..
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 228ms DFS 치킨가게 중 M개를 선택할 때, 각 집의 치킨 거리 합의 최소값을 구하는 문제이다. 치킨가게의 좌표와 집의 좌표만 필요하므로 입력되는 값들을 이차원 배열에 저장하지 않아도 된다. 두 개의 List 를 선언하여 치킨가게 좌표와 집의 좌표를 따로 저장해주었다. 치킨가게를 포함하는가 포함하지 않는가의 문제로 DFS를 이용하였으며 치킨가게의 포함 여부를 판단하기 위해 boolean[] 배열을 추가로 선언해줬다. M개의 치킨가게를 선..
