네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 2. 풀이 과정 특정 상태까지의 최소 이동 시간을 구하기 때문에, BFS로 탐색하였다. 여기서 고민했던 부분은 방문 체크였다. 이미 이전에 고려했던 2차원 배열의 상태는 다시 볼 필요가 없기 때문에, 이 2차원 배열을 int형 숫자하나인 123456780 식으로 변환해서 방문체크를 하고 너비우선탐색을 진행했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; p..

1. 문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 2. 풀이 과정 최단 경로를 구하는 데, 경로의 cost가 음수가 될 수 있기 때문에 Bellman-Ford 알고리즘을 사용했다. 평소에 잘 풀어보지 않았던 유형이라서 시간이 걸렸다.. 벨만-포드 알고리즘은 다익스트라와 유사한데, 다익스트라는 현재 연결된 노드에서 갈 수 있는 경로를 살펴보며 값을 업데이트하는 반면 벨만-포드 ..

1. 문제 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 2. 풀이 과정 처음엔 DFS로 모든 경로를 처음부터 끝까지 탐색하도록 했고, 시간 초과가 났다. 아래 그림과 유사하게, 출발점에서 도달할 수 있는 좌표에 +1을 해나가며 값을 업데이트하고 결과는 (N, N)의 값을 출력해주면 된다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.uti..

1. 문제 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 2. 풀이 과정 처음엔 ArrayList로 구현했다가 N의 범위가 100보다 작아서 2차원 배열이 더 빠를 것 같아서 수정했더니 2배 빨라졌다. 배열의 처음과 끝이 이어져있기 때문에 1번 과정에서의 8방향 탐색은 나머지 연산을 활용했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.uti..

1. 문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 2. 풀이 과정 상근이가 이미 지나간 곳은 불이 번져도 상근이를 따라 잡을 수 없기 때문에, 불이 번지는 건 빈칸만 고려해주었다. 빈칸을 누가 먼저 가냐만 보면 된다. 상근이가 현재 갈 수 있는 위치와 불이 방금 번진 위치를 모두 queue에 넣고, 4방향 탐색으로 갈 수 있는 곳에 표시를 해준다. 이때, 상근이는 불이 다 번지고 난 후에 움직이기 때문에 처음 상근이의 위치는 queue의 마지막에 ..

1. 문제 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 2. 풀이 과정 손에 든 계란으로 어떤 계란을 칠 지에 따라 DFS탐색을 한다. DFS가 끝나면 다른 길 탐색을 위해, 이전에 바꿔준 변수를 되돌려준다. 이때 주의할 점은 두 가지였다. 여기서 자기 자신은 깰 수 없다는 것과 손에 든 계란이 깨질 경우와 친 계란이 깨질 경우를 모두 고려해서 cnt를 증가시켜야 한다는 점이다. import java.io.BufferedRea..

1. 문제 https://www.acmicpc.net/problem/19583 19583번: 싸이버개강총회 첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59) 각 시간은 HH:MM의 형식으로 주어진다. 두번째 줄부터는 www.acmicpc.net 2. 풀이 과정 시간을 ":"을 기준으로 잘라서 int로 변환하여 분단위로 비교하였다. 시작시간보다 빨리 채팅을 친 사람들을 Set에 넣으며 중복 제거를 함께 해주었다. 종료시간과 스트리밍 종료시간 사이에 채팅을 친 사람은 Set에서 빼주면서 결과값을 구하였다. 추가적으로 입력이 언제 종료되는지 모르기 때문에, EOF검사를 해주어야 한다. Scann..

1. 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 풀이 과정 보통 DFS, BFS를 같이 쓸 수 있는 문제가 많아서 대부분 DFS로 풀다가 이번에 오랜만에 BFS 방식으로 풀어서 어색했다. 가능한 경로 중에서 최소 길이를 찾는 문제라서 BFS 방식으로 풀어야 한다. 풀이 방식을 간단하게 설명하면, Queue에 방문할 수 있는 층수를 넣고 Queue의 크기만큼 반복문을 돌며 다음 단계에 방문할 수 있는 층을 찾는다. 이미 방문한 층은 다시 방문..

1. 문제 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 과정 가로, 세로 따로 보고 겹치는지 확인해주면 된다. 즉 각 길간에는 경사로가 겹치는지는 확인할 필요 없다. 경사로로 갈 수 있는지는 1칸 오르막 길과 1칸 내리막 길 2가지 경우로 나눠서 생각해줬다. '오르막길'의 경우, 길 하나를 탐색하면서 현재 보고 있는 값과 같은 값이 몇 개 연속으로 나왔는지 저장하고 있다가 오르막길을 만났을 때 그 개수가 L개 이상이면 pass, 아니면 return fa..

1. 문제 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 2. 풀이 과정 DFS, BFS 탐색 문제인데, 고민했던 부분은 방문체크를 어떻게 할 지였다. 방문체크는 A, B에 부었던 물의 양으로 2차원 배열을 사용했다. A, B의 물의 양이 정해지면 C의 물의 양도 정해지기 때문에, 2차원 배열로 물통들의 상태를 방문 체크 해줄 수 있다. 아래 푼 방식은 DFS를 사용했다. A에 있는 물의 양이 0보다 크다면 B, C 각각 ..