본문 바로가기

백준154

백준 c++ 21609 "상어 중학교" -[PlusUltraCode] https://www.acmicpc.net/problem/21609 21609번: 상어 중학교상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록www.acmicpc.net [필자 사고]BFS 구현문제다.조건들이 어마무시해서 한글자라도 잘못 읽으면 골로가는 문제다.중요 조건들은 독자들이 잘 읽기를 바라며 이 문제에서 챙겨야 되는 핵심 개념들을 공부해 보겠다. 먼저 vector를 이용한 정렬 시스템 정의다. bool cmp(Node a , Node b){ }  형태로 작성된다. return true 형태로 작성하면 a 랑 b 형태로 순서가 되고return false 형.. 2024. 3. 18.
백준 16933 c++ "벽 부수고 이동하기 3" -[PlusUltraCode] https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net [필자 사고] 이 문제는 너비우선 탐색을 이용한 BFS탐색 문제이다. 벽 부수고 이동하기1,2를 풀어 봤을 것이다. 벽 부수고 시리즈의 공통점은 1이라는 해당 장애물이 있어 능력을 이용해 이 벽을 부술지 말지 결정하는거다. 다른 문제와 다르게 이 문제만의 특이한 점은 밤과 낮에 행동하는 방식이 다르다는 점이다. 필자는 처음에 밤과 낮에 따라 방문되는 지점이 다른.. 2024. 3. 14.
백준 16946 c++ "벽 부수고 이동하기4" -[PlusUltraCode] https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net [필자 사고] 벽 부수고 이동하기 1,2,3,4 중 시리즈 문제이다. 대부분의 벽 부수고 문제는 벽을 부순다음 BFS탐색을 시작해야 됬다. 이 문제 또한 이전과 같은 방식을 사용하게 되면 시간이 초과된다. 따라서 필자는 0으로 되어있는 칸을 미리 전처리 탐색을 해줘서 이동할 수 있는 칸의 값을 부여해 줬다. 그 다음 마지막에 1인 불록 상,하,좌,우만 검사하여 각각 더해줬다... 2024. 3. 13.
백준 14442 c++ "벽 부수고 이동하기 2" -[PlusUltraCode] https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net [필자 사고] 이 문제는 BFS업그레이드 문제이다. 이 문제를 풀기 시작했따면 장애물이 있을 때 BFS탐색 문제를 많이들 풀어 봤을 것이다. 장애물 BFS에 더불어서 visited[][][] 3차원으로 작성하여 벽을 부술 수 있는 능력까지 체크해주면 쉽게 풀 수 있다. [소스 코드] #include #include #include #include using na.. 2024. 3. 12.

티스토리툴바