목록알고리즘/백준 (341)
어흥
문제 링크: https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘에 대해 알고 있어야 한다 2. 구현 - 1번 Node부터 각 Node까지의 거리를 MAX로 초기화한다 - 간선에 대한 정보를 V[] 벡터에 담는다 - 우선순위큐를 사용하여 다익스트라 알고리즘을 구현한다 #define MAX 987654321 #include #include #include #include using namespace std; struct ..
문제 링크: https://www.acmicpc.net/problem/18235 18235번: 지금 만나러 갑니다 첫 번째 줄에 세 정수 N, A, B가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ A, B ≤ N, A ≠ B) www.acmicpc.net 1. 주의할 점 - 구간은 [1,len]이다 - 같은 점을 다른 Day에 방문할 수 있다 Ex) 구간: [1,10] 시작위치: 5 목표위치: 4 방법1: 5 → 4 방법2: 5 → 6 → 4 방법3: 5 → 6 → 8 → 4 각 방법으로 5→4로 갈 수 있는 날은 1,2,3일에 모두 도달 가능 2. 구현 - Arr[] 배열을 통해 해당 위치에 방문한 날을 적는다 - Info 구조체를 이용하여 현재 위치, 날, 점프 거리를 담는다 - Queue를 ..
문제 링크: https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 1. 주의할 점 - 구현할 부분이 많다 - 구슬을 어떻게 당길 것인가? - '파괴된'과 '폭파된' 구슬은 같지 않다 2. 구현 - Info 객체를 이용하여 1~Num^2-1까지 구슬의 위치를 V[] 배열에 담는다 - Arr[][]를 이용하여 현재 격자에 존재하는 구슬의 번호를 나타낸다 - Init() 함수를 이용하여 V[] 배열을 채운다 - M번 동안 지문에서 말한 ..
문제 링크: https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 1. 주의할 점 - 순서대로 정확히 구현을 한다 - 각 단계가 끝나고 초기화해야 할 부분들을 살핀다 2. 구현 - 배열의 범위와 방향을 1씩 줄인다 - Arr[][] 배열에 바구니의 상태를 담는다 - 최초에는 구름이 정해진곳에서 생성되므로 4구역을 Cloud 벡터에 담고 시작한다 - 각 단계가 시작하기 전에 init()을 통해 구름이 사라진곳을 나타내는 Check[][] 배열을..
문제 링크: https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 1. 주의할 점 - 모든 사항에 대해 정확히 구현한다 - 초기화를 잘 진행한다 - 끝나는 조건을 확인한다 - 무지개돌에 대한 처리를 잘 수행한다 2. 구현 - 격자에 대한 정보를 입력 받을 때, 무지개 돌의 색을 M+1로 바꾼다 - While문을 통해 BFS(), Gravity(), Rotate(), Gravity()를 순서대로 수행한다. 이때, BFS이후 finish의 값이 Tr..
문제 링크: https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 1. 주의할 점 - 우선순위 큐 정렬을 잘 정리한다 - 요구에 맞게 정확히 구현한다 2. 구현 - Arr[][] 배열을 통해 해당 자리에 위치한 학생 번호를 저장한다 - favorPeople[] Set을 통해 해당 학생이 선호하는 학생 번호를 저장한다 - score[] 배열을 통해 선호하는 학생들의 수에 해당하는 점수를 반환한다 - 배치할 학생들의 순서를 people 큐에 ..
문제 링크: https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 1. 주의할 점 - 매 TC마다 초기화 작업을 수행한다 - Stahler가 1 늘어나는 기준을 이해한다 2. 구현 - 모든 간선에 대한 정보를 Li[] 에 담는다 - Conn[] 배열을 통해 해당 Node로 도착하는 Node의 수를 저장한다 - Counting[]을 통해 각 Node에 도착한 Stahler 번호를 저장한다. 이때 Stahler번호가 1개도 없었다면 추가, 1개라도 ..
문제 링크: https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 1. 주의할 점 - 위상정렬에 대해 알고 있어야 한다 - 해당 건물이 여러개 지어질 수도 있다 2. 구현 - Li[]를 통해 선행관계를 저장한다 - Building[]을 통해 각 건물이 지어진 수를 저장한다 - Conn[]을 통해 해당 건물을 짓기위해 선행되어야 하는 건물 수를 저장한다 - 각 조건에 따라 치트키 사용여부를 판단한다 import java..