# BFS
그래프 순회
트리와는 다르게 그래프를 순회할때는 시작점을 정해주어야 한다.(그래프에는 루트가 없기 때문.)그래프에서는 깊이라는 개념이 모호한데, 인접점의 인접점을 따라 길이 막힐때까지 가는 것을 의미한다.1\. 각 vertex의 인접점을 해시 테이블에 담아둔다. 2\. 시작점을 정
[백준 15686. 치킨 배달]
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터
[백준 14502. 연구소]
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어
[python] 뱀과 사다리 게임_백준16928번(bfs)
이 문제는 최소 주사위 횟수를 구해야 하는 bfs 문제이다.전에는 너비우선탐색을 하며 전의 값 + 1만 해주면 되었다면, 이 문제는 이 값이 뱀이나 사다리가 있는지에 따라 경우가 추가되는 문제다.그래서 visited 정보를 따로 저장해주었고, board에는 0으로 초기
6087 레이저 통신
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레
[프로그래머스] 카카오프렌즈 컬러링북 (Java)
프로그래머스 카카오프렌즈 컬러링북https://school.programmers.co.kr/learn/courses/30/lessons/1829몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산한다.영역이란 상하좌우로 연결된 같은 색상의 공간을 의미
[BOJ] 17836번 공주님을 구해라!(C++) - 방문 배열에 대한 고찰
겉보기에는 그냥저냥 무난한 난이도의 그래프 탐색 문제다.최소 탐색시간을 찾아내는 문제라, BFS 로 접근해야하는 명확성이 보였다.하지만 약간 애를 먹었던 부분은 내가 방문 배열을 3차원이 아닌 2차원으로 설정했다는 것이다.완성 코드를 살펴보자.예시 데이터를 넣고 코드를
BFS ( Breadth - Frist Search) 너비 우선 탐색 알아보기 !
그래프 탐색 알고리즘정점들과 같은 레벨에 있는 형제 노드들을 먼저 탐색 하는 방식한 단계 씩 내려가면서 현재 노드와 같은 레벨에 있는 형제 노드들을 먼저 순회함.출처 : https://www.fun-coding.org/큐를 활용 하기 !크게 두개 활용1) 방문
[백준] 1926 그림 (JS)
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다
[Programmers] 미로탈출
문제 설명1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이
[프로그래머스] 게임 맵 최단거리 (BFS)
최단거리는 BFS로 푼다!!!!!!!!!!!!!!암기암기암기암기while 조건으로 queue길이가 0일 때다음으로 지나갈 곳이 없으면 queue.push가 발생하지 않아 queue는 텅텅 비어요shift를 이용하면 두 갈래 길이 나와 갈라지더라도 각각 한 번씩 진행돼요
[프로그래머스] 게임 맵 최단거리
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의
11724번 : 연결 요소의 개수 - Python
문제 https://www.acmicpc.net/problem/11724 풀이 DFS를 이용해서 연결 요소들을 카운트 한다. DFS를 한번 했다는 것은 1개의 연결 요소를 구했다는 말이다. 물론 BFS로도 풀 수 있다. 파이썬에서 DFS를 이용해서 풀다가 RecursionError가 날 수 있다. 제귀 깊이의 한계때문에 나는 Error이니 제귀 깊이를 변...
[프로그래머스] 리코체 로봇 (파이썬)
문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/169199전형적인 bfs 탐색 문제에서 상하좌우 조건 부분만 수정한다.상하좌우 탐색시 벽에 부딪히거나, 장애물을 만났을 경우까지 이동시킨다.vi
백준 12100 2048(Easy)
백준 12100←클릭DFS를 이용하는 문제이다. 문제의 제한조건에서 DFS의 길이가 5층으로 제한되어 있기에 시간 복잡도는 크지 않다. DFS를 사용하는 것 보다 문제를 구현하는 것이 조금 귀찮은 문제다.n: 현재 DFS의 층에 해당한다. d: 움직임의 종류이다. 0부
[JAVA] 백준 1175 배달
백준 1175https://www.acmicpc.net/problem/1175어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의