Algorithm/Algorithm Problem

SWEA 1953 탈주범 검거(BFS, 구현)

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 구현단계에서 생각보다 애를 먹었던 문제다. 문제접근은 시작점에서 bfs를 돌리면서 인접한 노드의 파이프모양에 따라 나아갈 수 있는 방향이 정해지고 그것을 카운트하는 방식인데 어떤 모양인지 체크하고 어떤 방향으로 갈지 체크하는 로직을 짜는데 시간이 많이 걸렸다. 먼저 상하좌우에 따라 각각 갈 수 있는 파이프의 번호를 저장해둔다(dir 배열) dx, dy 방향벡터는 상하좌우로 이동할 수 있지만 지금 내가 위치한 파이프의 모양에 따라 상하좌우 중 특정 방향으로만 갈 수 있기 때문에 상하좌우의 벡터를 파이프의 개수 7개 만큼 dx[7][4], dy[7][4]로 만들어 이..

SWEA 1952 수영장(DFS, DP)

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 수영장을 어떠한 기준으로 끊어야할지 모르기 때문에 모든 경우를 봐줘야한다. DFS의 구조를 트리로 그리면 이해가 쉬워진다. 기간은 1년이기 때문에 1년에 해당하는 부분은 상수(final)일 것이고 1일, 1개월, 3개월 단위로 어떤 순서로 할지 모든 경우를 탐색한 다음 비용을 갱신해주면서 답을 찾는다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Solution{ static int[] price, data; static ..

백준 19238 스타트 택시(BFS, 구현)

19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 택시가 서있는 위치에서 여러손님들 가운데 최단거리에 있는 손님 먼저 채우고 손님 목적지 까지 태우는 단순한 구현 문제이다. 이 문제가 까다로웠던 이유는 한 손님의 운송이 끝나면 그 손님에 대한 방문처리를 해줘야하는 것과 어떤 손님을 먼저 태울지에 대한 우선순위 조건이 2개나 있어서 조건문을 구현하기 힘들어서 어려웠다. 최단경로를 구할려 할 때 플로이드-와샬을 쓰려고 했지만 가중치가 나오지 않았기 때문에 그냥 BFS를 써서 그..

백준 2623 음악프로그램(위상정렬, DFS, BFS)

2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 재미있는 문제였다. 각 PD들이 가수들의 무대순서를 정하고 각각 PD에 요청에 모두 부합하는 완벽한 순서를 만들어내는 것이 문제다. 먼저 문제를 읽고 생각을 해봤을 때 순서라는 점이 가장 Key-Point라는 생각이 들었다. 따라서 순서라는 점을 계속 기억하고 인지하기 위해 Queue, Stack이라는 자료구조를 통해서 기억했으면 좋겠다라는 생각을 했고 더 나아가서 이 자료구조를 통해서 Next step까지 생각하는거니까 DFS, BFS문제구..

백준 3967 매직 스타(DFS)

3967번: 매직 스타 매직 스타의 모양이 주어진다. 수가 채워져 있지 않은 곳은 x로, 채워져 있는 곳은 'A'부터 'L'까지 알파벳으로 채워져 있다. i번째 알파벳은 숫자 i를 의미한다. '.'는 매직 스타의 형태를 만들기 www.acmicpc.net 문제는 어렵지 않았지만 시간초과에 대해서 많이 고전한 문제다. 단순히 빈칸에 대해서 사용할 수 있는 알파벳을 하나씩 넣어보고(완전탐색) 합이 26이 되면 종료하는 문제 근데 여기서 문제는 완전탐색을 해버리겠다고 한다면 빈칸에 대해서 넣어볼 수 있는 알파벳 여러개를 한번씩 모두 넣어본다는 것(순열)인데 이 문제는 그런 모든 경우를 구하는 문제가 아니다. 아래 코드에 보면 DFS의 재귀부분에 break;를 넣었는데 이 부분이 매우 핵심적인 부분이다. 문제에..

백준 20055 컨베이어 벨트 위의 로봇(구현)

20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 걸린시간 : 1시간 30분 문제자체는 어렵지 않았는데 어떤 자료구조를 써야되는지 확실하게 정하지 못하고 고민을 너무 많이 하다가시간을 많이 썼다. 원형 돌리기를 만나면 자꾸 python의 deque.rotate()를 먼저 생각하는 버릇이 있어서 Java에서 Collections.rotate()를 쓰려는 버릇이 있는데 고쳐야겠다고 생각이 들었다. ----유의해야할점---- robot은 n-1에서 무조껀 빠지기 때문에 robot을 관리하는 배열의..