5014 스타트링크 알고리즘 (BFS) - 직선으로의 BFS 를 사용하면 됨 - DP를 사용하면 시간초과가 발생함. - 도달시 다 종료한다고 해도, 그게 최소로 간건지 몰라서 결국 더 검사해야함. 코드 #include <iostream> #include <list> using namespace std; list<...

4991 로봇청소기 알고리즘(BFS, 브루트포스) 1. 구현이 더 중요한 문제. 2. 그냥 시작 + 각 더러운 곳(DT) 에서 다른 DT로의 최소 거리를 저장한 2차원 배열을 BFS로 만들고 3. 시작부터 모든 경로를 탐색하여 최소 거리를 뽑아내면 됨. 4. 방문 할 수 없는지 판별은 시작에서 갈 수 없는 DT가 있는지 확인하면 됨 구현 1....

4811 알약 알고리즘 (dp) 1. 하나의 완전한 알약을 one, 반쪽 알약을 half 라고 하면, dp[1001][1001] 를 선언하고, one, half를 기준으로 dp를 저장함 2. dp를 진행하면서 밑으로 내려가면서 one이 1개 이상이면 1 줄이고 half 1 증가하고 밑으로 내려갈 수 있고, half가 1개 이상이면 마찬가지로. ...

4386 make constellation 알고리즘(MST) 1. 모든 별들 사이의 거리를 구한 다음에, 두 별의 위치, 거리를 저장한 구조체 배열을 거리순으로 오름차순 정렬 2. 구조체 배열에서 하나씩 빼가며 크루스칼 시행 -> edge == numOfStar -1 이면 중지 후 출력 코드 #include <iostream>...

3197 백조의 호수 알고리즘(구현) 처음 방법 1. 한 백조에서 BFS 실시하여 다른 백조를 만날 수 있는지 검사 2. 전체 맵을 검사해서 녹일 수 있는 걸 녹임 3. day 추가하고 다시 1부터 -> 시간이 너무 걸림. 특히 맵 초기화하는 부분이 많이 걸림 두번째 방법 1. 1번은 유지 2. 녹을 수 있는 얼음만 저장한 q에서 ...

3190 Samsung sw test 알고리즘 1. 그냥 대가리 옮기고 꼬리 잡히는지, 칸 밖인지 확인하고, 또 사과있는지 확인하고, 또 시간이 바꿀때가 됐는지 확인 2. 뱀 몸은 vector로 저장 / 사과 위치는 2차원 bool 배열로 저장하여 메모리랑 참조시간 아낌. / 시간은 Direction 구조체에 저장하고, directionInde...

2933 미네랄 알고리즘(구현, 시뮬레이션) 1. 들어온 위치의 미네랄을 지움 2. 지운 위치에서 상하좌우에 인접한 칸들을 root로 BFS 시행 -> 바닥에 닿는 칸이 있으면 공중에 뜬 클러스터가 아님 3. 공중에 뜬 클러스터이면 BFS 시 넣은 칸들을 열순, 열이 같으면 행이 큰 순으로 정렬 4. 각 열별로 가장 밑에 있는 칸만 검사하여 ...

2931 가스관 알고리즘(구현) 1. M에서 시작해 갈 수 있는 방향으로 가다가 빈칸을 마주하면 스탑. 만약 빈칸이 없으면 아예 처음부터 연결이 안된 것. 이때는 Z 부터 시작해 빈칸을 찾는다. 2. 빈칸을 찾으면 빈칸 주변을 검색. 인접한 칸에 바로 연결되는 파이프가 있으면 그 칸을 true로 표시. 표시된 것에 따라 빈칸에 넣을 수 있는 가...

2887 planet tunnel 알고리즘(정렬, MST) 1. 모든 행성들의 x좌표, y좌표, z좌표를 꺼내 따로 저장하고, 오름차순으로 정렬 2. 정렬한 것에서 인접한 것끼리 비용을 계산, (인접한 점 두개 + 비용)을 구조체로 n-1개의 원소를 가지는 배열 3개를 선언하고 집어넣음 3. 그 구조체배열 3개는 비용을 기준으로 오름차순으로 정렬 ...

2568 전기줄 알고리즘(LIS) 1. LIS를 구하면 그것들이 겹치지 않고 최대로 연결가능한 전깃줄들이다. 2. 따라서 LIS를 구하고 전체 전깃줄에서 LIS를 빼면 빼야하는 전깃줄의 수와 전깃줄의 종류가 나오게 된다. 코드 #include <bits/stdc++.h> #define MAX_WIRE 100001 using nam...