Young

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 오늘은 2020 카카오 코딩테스트 풀이 다섯번째 시간 입니다. 이번 문제는 아주 전형적인 BFS + 구현 문제 입니다. BFS의 기초는 https://yomyom0824.tistory.com/3?category=1081200 여기에서 익히고 오시면 됩니다. 여기서 배울 부분은 단순 동서남북 이동에 대한 것보다는 '회전에 대한 것' 입니다. 1 2 3 4 5 6 7 8 9 10..

https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 문제 오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다. 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다. 일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 로봇은 www.acmicpc.net 오늘 또한 완전탐색입니다. 지도가 주어졌을 때 최단거리는 보통 BFS로 구하게 됩니다. 하지만, 최대 10개가 주어지는 더러운 칸을 어떤..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다. 마왕은 용사가 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출 www.acmicpc.net 딱 두가지 경우만 생각해보면 된다. 1. 전설의 명검없이 바로 공주가 있는 곳으로 간다. 2. 전설의 명검이 있는 곳으로 간..

https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 문제 소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다. 존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다. K마리의 (1 ≤ K ≤ 100, www.acmicpc.net 개인적으로 해석을 문제를 햇갈리게 하여, 영어로 문제를 읽는걸 추천한다. (r,c) - (r`,c`) 의 의미는 이..

https://www.acmicpc.net/problem/14172 14172번: Moocast Write a single line of output containing the maximum number of cows a broadcast from a single cow can reach. The originating cow is included in this number. www.acmicpc.net 소들이 메시지 전달할 수 있는지는 O(N^2)으로 모두 조사합니다. 문제에도 나와있지만, 한 가지만 주의하면 됩니다. (A -> B로 갈 수 있다) != (B - > A로 갈 수 있다) 두 소의 워키토키의 power에 따라 메시지를 보낼 수 있는지를 조사해봐야 합니다. 모두 조사를 한 다음, 모든 소들을 ..

https://www.acmicpc.net/problem/11975 11975번: Build Gates The first line of input contains \(N\) (\(1 \leq N \leq 1000\)). The next line contains a string of length \(N\) describing FJ's path. Each character is either N (north), E (east), S (south), or W (west). www.acmicpc.net 이번 문제는 문제는 참 이해하기 쉽고, 직관적인데 반해 이걸 구현하려니 불편한 점이 한가지가 있습니다. 보통은 정점을 타고 들어가면서 flood fill을 수행해야 하는데 정점 사이를 이어서 fence를 놓는다는 ..

컴퓨터로 문제를 풀 때, 보통 그 문제는 탐색을 기반으로 합니다.문제가 정의하고 있는 '공간'을 탐색합니다. 상태를 논리적으로 정의할 수 없다면, 모든 공간을 커버한다는 보장이 없기 때문에해가 맞는 것인지 판별할 수 없습니다.그 다음 공간은 이전의 상태를 통해 발생하기 때문에, 트리처럼 공간이 뻗어 나갑니다. 그 공간을 방문하는 방법 중에 'BFS'와 'DFS'가 있습니다. 지금은 BFS(Breadth First Search)를 설명하려고 합니다. 영어 뜻 그대로 넓이 우선 탐색이다. 트리의 가지를 따라서 무작정 들어가지 않고, depth를 하나씩 늘려갑니다. 아래는 BFS와 DFS를 비교하는 그림입니다. 문제에 따라 어떤 방문 방법을 선택해야 정답을 빠르게 찾을 수 있을 것인지판단하고 적용해야 합니다...