# BFS
4연산 14395
BFS를 활용하여 4연산을 수행해주면 된다고 생각했다. 하지만 4연산 중 2연산은 같은 자리를 계속 지정해준다. 나누기는 계속하여 자신을 나누기에 1이 나오고 뺄셈은 계속하여 자신을 빼기에 0이 나온다. 즉 반복할 필요가 없는 요소이다.그것을 해결하기 위해선 뺄셈은 무
[BOJ] 4179번 불!(C++)
소요시간 : 2시간 이상90분정도 걸려서 실수가 없다는 판단을 하고 제출했으나, 메모리 초과가 발생했다.아직 구현하는데 시간이 많이걸리는 것 같다. 메모리 초과가 발생한 이유는 사소한 실수라기 보다는 방법론적인 차이가 있었다. 문제를 쉽게 풀어내지는 못했지만, 얻어가는
[BaekJoon] 16947 서울 지하철 2호선 (Java)
https://www.acmicpc.net/problem/16947지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개가 있습니다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있습니다.2호선은 순환선 1개와 2
물통 14867
BFS로 풀면 된다. 빨리 최소 작업 수에 도달하기 위해서는 BFS로 푸는 것이 좋다.수작업으로 F, E, M에 대한 6개의 경우를 모두 입력할 수도 있지만 중복된 부분은 없애주는 게 나을 거 같아서 배열을 이용하였다.처음에는 배열로 방문 확인을 하였다. 하지만 문제가
너비 우선 탐색(Breath First Search)
너비 우선 탐색은 말 그대로 탐색을 수행하는 알고리즘으로, 너비를 우선으로 한다. 이는 최단 경로 탐색에 많이 사용되며, 자료구조 중 큐(queue)를 사용한다는 특징이 있다.
1707번 : 이분그래프 - Python
문제 https://www.acmicpc.net/problem/1707 풀이 BFS를 이용해서 그래프를 탐색한다. 노드를 방문할때마다 group으로 표시를 한다. 연결되어 있는 노드와 같은 group인지 판단하면서 이분그래프를 판단한다. 코드
코딩테스트 마스터의 길 (2)
앞으로 누누이 얘기할 것이지만 이건 "알고리즘 마스터를 위한 길" 이 아니다.다수의 서류전형 탈락 경험이 있는 사람이라면 이 문구만 봐도 탈락의 짙은 향기를 맡을 수 있다...... 라고 생각할 뻔 했다. 밑에 코딩 테스트 결과를 기반으로 다음 전형 진행여부를 결정 한
[백준] 13460번 구슬탈출 2(파이썬)
난이도 : GOLD I > 문제링크 : https://www.acmicpc.net/problem/13460 삼성 sw 역량 테스트 문제이다 문제해결 해결하지 못해서 다른풀이에서 영감 받았다. 파란공과 빨간공 bx,by rx,ry 로 저장한다. 구멍이나 벽을 만날 때까
[알고리즘] DFS & BFS
DFS(Depth-First Search) > 깊이 우선 탐색 재귀 구현 (비교적 간단) 스택을 이용한 반복 구조로 구현 직관적이라 이해가 쉽다 실행 속도 더 빠르다 BFS(Breadth-First Search) > 너비 우선 탐색 다익스트라 알고리즘 등에 유용하게 사용된다 BFS는 재귀로 동작하지 않고,* 큐를 이용한 반복 구현만 가능하다* 큐를...
[BaekJoon] 23288 주사위 굴리기 2 (Java)
https://www.acmicpc.net/problem/23288명우기업은 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하는지 결정하지 못했습니다.집하장들 사이의 경로와 해당 경로로 이
노드사이의 거리 1240
트리를 탐색하며 해당하는 위치를 찾으면 된다. 탐색하는 과정에서 방문하는 곳에 거리의 값을 합해가면 두 노드 사이의 거리를 찾을 수 있다.처음에는 플로이드 워셜로 풀려 했다. 풀리긴 하였지만 최대 1,000^3만큼의 작업을 하기에 실행 시간이 꽤 걸렸다.BFS를 활용하
(백준 - 1245) 농장관리 - 파이썬, 자바
출처 : (https://www.acmicpc.net/problem/1245)문제를 보면 그래프 탐색임이 한눈에 보입니다.문제를 이해하고 로직을 정해보았습니다.산봉우리의 높이가 주변의 봉우리보다 낮다면 False주변의 산봉우리 중 산봉우리와 동일한 높이가 있다
[BackJoon]DFS와 BFS<1260번>
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.첫째 줄
그래프 순회
트리와는 다르게 그래프를 순회할때는 시작점을 정해주어야 한다.(그래프에는 루트가 없기 때문.)그래프에서는 깊이라는 개념이 모호한데, 인접점의 인접점을 따라 길이 막힐때까지 가는 것을 의미한다.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으로 초기