목록BFS (89)
어흥
문제 링크: https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 1. 주의할 점 - 구현해야 하는 조건이 많다 - 2개의 좌표를 어떤 방식으로 저장할 것인지 정한다 2. 구현 - BFS를 통해 문제를 해결한다 - Info 객체를 통해 로봇의 정보를 저장한다. 로봇의 한 좌표와 어떤 방향에 다른 좌표가 위치해 있는지 저장한다. - 우선순위큐 pq에 로봇의 정보를 담으며, 소요 시간의 오름차순으로 정렬한다 - Board의 정보를 static 변수..
문제 링크: 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://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://programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 1. 주의할 점 - 같은 색일때에만 큐에 넣는다 2. 구현 - Check[][] 배열을 초기화한다 - Pictures[][] 배열에 대해 0이 아니고 확인하지 않은 곳이라면 BFS를 수행한다 - 4가지 방향 탐색을 하며 같은 색이고 방문하지 않았다면 Queue에 추가한다 #include #include #include using namespace std..
문제 링크: 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/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..