어흥

문제 링크: https://www.acmicpc.net/problem/24513 24513번: 좀비 바이러스 여기 $N$ x $M$ 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 $1$ www.acmicpc.net 1. 주의할 점 - BFS 종료시점을 잘 정하여 TLE가 나지 않도록 한다 - 동시에 도달할 경우, 어떻게 처리할 것인가 2. 구현 - Y, X, 바이러스 번호, 해당 칸에 도달하기까지 걸린 시간의 형태를 저장하는 Info를 이용하여 BFS를 수행한다 - Check[y][x][flag] 배열을 통해 flag 바이러스가 [y][x]에 도달하기까지 걸린 시간을 저장한다 - Ar..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/1837?language=java 코딩테스트 연습 - GPS edge_list [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 6], [5, 6], [5, 7], [6, 7]] programmers.co.kr 1. 주의할 점 - BFS/DFS로 시도하면 TLE 혹은 '틀렸습니다'라는 문구가 출력된다 - DP로 접근한다 2. 구현 - 단순하게 그래프 문제라고 생각하고 DFS/BFS로 접근했다가 TLE와 '틀렸습니다'의 연속..(다만 이때, 1개의 채점에 여러개의 TC가 존재하여 1개라도 TLE 또는 메모리초과 발생시 틀렸습니다로 나타난다는 사람들의 의견이 존..

문제 링크: https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 1. 주의할 점 - 0과 -1을 출력하는 기준을 정확히 알아야 한다 2. 구현 - init() 함수를 통해 Check[][] 배열을 초기화한다. Check[][] 배열은 정답 배열이다 - 지도에 대한 정보를 Arr[][]에 받으며, 목표지점에 대한 정보를 Sx, Sy에 저장한다 - BFS 탐색을 통해 목표지점에서 도달할 수 있는 지점까지의 ..

문제 링크: https://www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net 1. 주의할 점 - 루머를 퍼트리는 일은 동시에 일어난다 2. 구현 - BFS의 방법으로 문제를 해결한다 - Info 객체를 사용하여 현재 사람의 번호, 루머를 들은 시간, 당시에 주변에 루머 믿었던 사람 수 - rumorTime[] 배열을 이용하여 루머를 믿는 시간을 저장한다. 초기에는 init() 함수를 통해 -1로 전부 초기화한다 - nea..

문제 링크: 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..

문제 링크: https://www.acmicpc.net/problem/17265 17265번: 나의 인생에는 수학과 함께 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 www.acmicpc.net 1. 주의할 점 - 이동 가능한 방법으로는 하하, 하우, 우하, 우우 총 4가지의 방법이 존재한다 2. 구현 - Check[][][] 배열을 통해 각 지점까지 이동할 때 얻을 수 있는 최대 및 최소값을 저장한다 - BFS() 함수를 2번 수행하여 한 번은 최대를, 다른 한번은 최소를 구하도록 한다 - BFS 탐색을 수행하기전, Check[][] 배열을 초기화하고 시작한다..

문제 링크: https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 1. 주의할 점 - N≤10^5이므로 간선들의 정보를 나타내는 2차원 배열을 사용하지 않는다 2. 구현 - 가장 높은 등수는 1+ (해당 학생보다 잘 본 학생 수) - 가장 낮은 등수는 전체 학생수 - (해당 학생보다 못 본 학생 수) - Check[][2] 배열을 통해 각 Node를 방문했는지 검사한다([][0]: 정방..

문제 링크: https://www.acmicpc.net/problem/2637 2637번: 장난감조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 1. 주의할 점 - 위상정렬로 접근한다 - 필요한 물품의 개수를 List 형태로 담지 않는다 → 메모리 초과 회피 2. 구현 - Info 형태의 구조체를 이용하여 A의 물건을 만들기 위해 Idx번째 물건이 Val만큼 필요하다는 것을 나타낸다 - Need[] 배열을 통해 필요한 총 물건의 수를 저장한다 - Conn[] 배열을 통해 연결된 상위부품의 수를 나타낸다..