어흥

문제 링크: 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/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 1. 주의할 점 - 특정 지점에 방문했을 때, 서로 다른 물건의 조합을 가지고 접근한 경우 어떻게 처리할 것인지 생각한다 2. 구현 - 위의 주의할 점의 예시로, (1,1)을 방문할 때 [0,1]번 물건을 가지고 접근했을 때와 [1,2]번 물건을 가지고 접근했을 때를 구분하기 위해 비트마스크를 이용한다(비트마스크 접근을 위한 추가 힌트: 최대 5개의 물건) - 집의 구조를 In..

문제 링크: programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 1. 주의할 점 - Check[][][] 배열이 갱신될 때마다 MOD로 나눈 나머지를 저장한다 - (Y,X)에 Dir의 방향에서부터 온 적이 여러번 있다면, 최종 경우에만 BFS를 수행하도록 한다 (안하면 메모리 초과 가능성↑) 2. 구현 - 2 방향으로만 이동가능하므로 항상 특정 지점까지의 거리는 최단거리로 구해진다 → Info 구조체를 큐에 삽입하여 B..

문제 링크: programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 1. 주의할 점 - BFS를 통해 해결한다 - Check[][][]를 통해 해당지점에 특..

문제 링크: www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 1. 주의할 점 - BFS 수행 도중, 0이 남아있지 않다면 BFS를 종료해도 된다 - 0이 없거나 극단적인 경우(Edge case)도 고려한다 더보기 TC #1 4 1 2 2 2 0 2 2 2 2 2 2 2 2 0 2 2 2 AC: 3 2. 구현 - 연구소에 대한 정보를 Arr[][]에 담고, 0의 개수를 Zero에 저장한다 - 바이러스의 좌표를 Virus 벡터에 담는다 - V 벡터를 통해 next_per..

문제 링크: www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net 1. 주의할 점 - BFS()를 통해 퍼트린다 - 최대한 간단하게 구현한다 2. 구현 - 한번에 퍼질 수 있는 정도를 Len[] 배열에 담는다 - 10개짜리 Queue를 생성하여 각 숫자에 해당하는 경우에만 포함하도록 한다 - 입력받을 때, 해당 지역이 성이면 개수를 센다 - BFS() 함수를 통해 1부터 P번까지의 Queue를 순서대로 퍼트린다 - Arr[][] 배열만을 사용하며, 다음 칸으로 ..

문제 링크: www.acmicpc.net/problem/5213 5213번: 과외맨 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 6, 1 ≤ i ≤ N * N - N / 2) 타일 i의 왼쪽에 쓰여 있는 숫자는 Ai, 오른 www.acmicpc.net 1. 주의할 점 - 타일에 대한 정보를 어떻게 저장하고 불러올 것인가 - 주변 타일을 어떻게 구할 것인가 - 끝까지 도달 못할 경우, 가장 번호가 큰 타일을 목적지로 한다 - 경로를 어떻게 저장할 것인가 2. 구현 - Arr[][]배열을 통해 각 타일에 대한 정보를 저장한다 - y와 x 벡터를 통해 각 타일이 2줄을 간격으로 Arr[][..

문제 링크: www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 1. 주의할 점 - 입력의 시작으로 1이 들어오는지 확인한다 - 2-2번의 조건을 정확히 처리한다 2. 구현 - 모든 간선에 대한 정보를 V[] 벡터에 저장한다 - 입력 받는 경로를 Order 벡터에 저장한다 - Finish[] 배열을 통해 방문했는지 체크한다 - inQueue[] 배열을 통해 현재 Queue에 있는지 확인한다 - Cnt를 통해 현재 비교해야 하는 번호를 가라킨다(Order[cnt]) - 큐에 1을 넣고 BFS를 시작한다. While문의 종료 조건으론 Queue가 비었거나 불가능한 경우다 - 현재 ..