너비 우선 탐색 (BFS)BFS(Breadth-First Search)란, 한 지점에서 다른 지점들을 방문할 때, 너비를 우선으로 모든 지점을 방문하는 것장점: 시작 지점으로부터 도착 지점까지의 최소 거리를 항상 구할 수 있다.단점: DFS에 비해 더 많은 메모리를 사용한다.특정 노드를 기준으로 “인접한” 노드를 우선적으로 탐색하는 방식이다. 즉, 시작 지점으로부터 가까운 노드를 우선적으로 방문하고, 멀수록 늦게 방문하게 된다. 이는 특히 거리 측정 알고리즘을 구현할 때 주로 사용될 수 있다. 주로 다차원 배열에서 특정 지점까지 걸리는 최소 시간을 구하는 문제에 BFS를 주로 사용할 수 있다. 코드로 구현하기 위해서는 Queue를 사용한다. BFS를 이용해 모든 지점을 방문하는 방법은 다음과 같다.비어있..

문제 링크Question총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.화합과 ..

문제 링크Question당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?Input입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 ..

문제 링크Question지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.불은 각 지점에서 네 방향으로 확산된다.지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.지훈이와 불은 벽이 있는 공간은 통과하지 못한다.Input입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.다음 입력으로 R줄동안 각각의 미로 행이 주어진다.각각의 문자들은 다음을 ..