BFS

드디어 드디어 푼 문제! 문제 설명을 올려준 산하언니께 무한한 영광을 드립니다. 사실 검색하고 찾아봐도, 왜 조합을 저렇게 하지? 저렇게 하면 완전탐색이 안되지 않나? 하면서 계속 궁금했는데, 산코중 덕분에 다른 방법을 찾았네융 시작-! 문제 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 설계 알고리즘 설계[접근방법] : 조합 + BFS 가장 먼저, 빈 공간인 X들 사이에서 3개를 골라야 한다. S X X T X X X X X S T..

BFS 문제 중에 가장 어렵게 푼 문제같다. 진짜 코딩테스트 문제였다면, 예시만 맞고 다 틀렸을 수도 있다.. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설계 알고리즘 설계 [접근 방법] : 완전 탐색 + BFS 풀이과정 1. 2차원 배열의 places를 반복문을 돌면서 하나의 배열씩 BFS를 돌린다. 2. BFS안에서 queue를 생성하고, 매개변수로 받은 String[] 배열을 2차원 배열로 변경한다. 3. 반복문을 돌면서 map..

무난한 BFS 문제! BFS와 DFS가 익숙해져가니 구현을 더 연습해야겠다. 문제 https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 설계 알고리즘 설계 [접근 방법] : BFS 무난한 BFS 문제다! 각각의 좌표가 상어가 있는 1의 지점으로부터 얼마나 멀어져있는지 확인하고, 가장 멀리 있는 거리를 출력하면 된다. 일단 상어가 있는 좌표를 찾고, 그 지점들로부터 8방향으로 탐색하며 그래프를 뻗어나가면 된다. 기준을 각각..

BFS 문제! 일반적인 BFS문제에서, 조금만 변형하면 시간이 많이 단축된다. 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 설계 알고리즘 설계 [접근 방법] : BFS 2차원 배열을 탐색하면서, 가장 빠른 길을 찾는 방법인 BFS로 풀었다. 특별할 건 없고, 평범한 BFS 문제다! 풀이 과정 1. 2차원 배열의 크기인 w와 h를 입력받는다. 그리고 2차원 배열인 map을 생성하고, 토마토 값을 입력받는다. 2. BFS ..

항상 생각하는 것이지만, 문제만 잘 읽으면 된다. 한 번 더 생각하기! 문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 설계 알고리즘 설계 [접근 방법] : BFS 가장 먼저 생각한 것은 DP지만, BFS로 푸는 것이 더 쉽겠다 싶어서 바꿨다. 배열을 arr을 생성하고 이 배열의 인덱스를 게임 번호로 생각했다. 그리고 그 배열의 값을 이 인덱스까지 오려면 얼마나 주사위를 굴려야 하나로 생각했다..

오랜만에 푼 BFS 문제! 한참 알고리즘 풀 때 DFS, BFS는 거의 자동으로 나왔는데 지금은 많이 생각하고, 고민하고 풀었다. 알고리즘은 정말 연습만이 답인듯 문제 https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설계 알고리즘 설계 [접근 방법] : BFS 가장 빠른 길 찾기 문제는 역시 BFS다. 이 문제가 일반적인 BFS문제와 다른 점은 한 칸 이동을 하나로 계산하는 것이 아니라, 벽을 만나거나 장애물을 만나서 멈추게 되는 상황까지 이..