미로 탐색  시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초192 MB208584960386089244.496%문제N×M크기의 배열로 표현되는 미로가 있다.101111101010101011111011미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.입력첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄..

그래프이미 DFS와 BFS에 대해서 글을 작성했지만, 그 전에 그래프에 대해 먼저 알고 가야한다. 그래프의 정의는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용하는것이고,간선은 방향이 없거나, 방향이 있을 수 있다. 코딩테스트에 자주 나오는 자료구조이므로 꼭 이해하고 있어야한다.탐색( DFS, BFS ), 트리에서도 사용한다. 그래프를 구현하는 3가지 방법은엣지 리스트 (순서에 맞게 배열에 저장하는 방식으로 사용 불편)인접 행렬 (2차원 배열 구조로 공간 복잡도 제약)인접 리스트 (ArrayList로 구현, 가장 많이 사용)인접리스트를 나도 가장 많이 사용했고, HashMap이나 ArrayList로 구현을 하면된다. 종류1. 가중치가 없는 ..

문제과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.입력첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.출력첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집..

드디어 DFS, BFS를 공부할 시간이 왔다.예전에 파이썬으로 코테 준비할때 찍먹한 적 있는데, 이번에 제대로 배워보려고한다.(사실 조합 & 순열 공부할 차례인데 DFS로 해야 제일 쉽게 풀 수 있단다,, 백트래킹에서도 써먹고) DFS&BFS는 그래프 탐색 알고리즘이라고도 한다. 대표적인 문제 유형경로탐색 유형 (최단거리, 시간)네트워크 유형 (연결)조합 유형 (모든 조합 만들기)DFS - 깊이 우선 탐색DFS는 루트 노드(or 일반 노드) 에서 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방식이다.주로, 재귀함수나 Stack으로 많이 구현한다고 한다.ex) 미로찾기에서 길을 찾다가 길이 막히면 마지막 갈래길로 돌아가는 방식 BFS - 너비 우선 탐색BFS는 DFS와 다르게 자..