프로그래머스 무인도 여행 https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전 나의 생각 BFS를 사용하여 공간을 탐색하는 문제다. 우선 식량이 있는 무인도를 탐색하기 위해선 양방향 탐색이 필요하다. 하지만 양방향 탐색을 하면서 오류가 날만한 상황을 모두 배제해줘야 한다. 1. 탐색할 다음 위치가 배열의 크기를 벗어나면 안된다. 2. 탐색할 다음 위치가 방문한 곳이 아니면서 X(바다)가 아니여야 한다. 두 조건을 만족할 시 다음 탐색 위치..
알고리즘 및 자료구조/BFS
백준 5427 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 풀이 전 나의 생각 이 문제의 정답률이 굉장히 낮은 이유는 조건을 설정하는 과정에 있어서 정확한 판단을 할 수가 없기 때문이라고 생각한다. 우선 차근차근 문제를 알아보자. 문제의 요약은 사람이 불에 닿기 전에 탈출을 할 수 있냐 없냐다. 이를 판단하기 위해선 불과 사람이 동시에 움직이는 조건으로 진행해야 한다. 그러면 동시에 진행하는 것 처럼 코드를 제작하여 풀면 되는 것이다. 그 방법으로는 먼..
백준 7569 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 전 나의 생각 다른 토마토 문제는 2차원 BFS였는데 뭔가 똑같은 이름의 토마토 문제가 하나 더 있어서 클릭해 봤다. 비슷하긴 한데 축이 하나 더 늘었다. 여기서 굉장히 헷갈렸는데 보통 2차원 배열만 사용하지 3차원 까지는 거의 사용하지 않기 때문이다. 그래서 이 문제를 풀려면 우선 3차원 배열의 개념부터 잡고가야 한다. C++의 3차원 배열은 arr[z..
백준 1926https://www.acmicpc.net/problem/1926 1926번: 그림어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로www.acmicpc.net풀이 전 나의 생각 BFS를 사용할 수 있는지 없는지에 따라 성공, 실패가 나뉠정도로 BFS의 기초적인 내용을 묻는 문제다. 문제의 포인트는 그림이 있는 곳을 방문하여 그림의 개수와 그림의 최대 크기를 구하는 것이다. 1. 그림의 시작점을 방문 하기 위해 for문으로 탐색을 진행한다. 2. 시작점에 도착했다면 BFS를 진행하여 그림의 길이만큼 방문 표시를 해준다 3. 크기는 큐의 pop횟수, 개..
