오뚝이개발자

문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 나의 풀이 BFS를 사용하여 풀었다. 걸린 시간 외에도 경우의 수를 카운트해야 하므로 방문 체크를 일반적인 방식으로 하면 안된다. 일반적인 경우처럼 방문한 곳은 다시 가지 않도록 하면 K까지의 경우의 수는 언제나 1이 되기 때문이다. 따라서 visit 체크를 2가지 경우로 나누어주어야 한다.(아래 코드 참고) 코드 # https://www.acmicpc...

문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 나의 풀이 bfs를 사용하여 풀면 된다. 1. bfs를 (0,0)에서부터 시작한다. 2. 도중에 공기칸을 만나면 큐에 넣어주고, 치즈칸을 만나면 1을 더해준다. 3. 한 번의 bfs를 돌고나서 값이 3 이상인 칸은 2면 이상이 공기와 접하는 것이므로 이 칸의 치즈를 0으로 만든다. 4. 1~3을 모든 치즈가 녹을때까지 반복 코드 #https://www.acmicpc.net/pro..

문제 https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cb14 Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com 나의 풀이 BFS를 사용하면 된다. 핵심은 상자가 많은 칸의 주변을 먼저 채워준다는 것이다. 이를 위해 우선순위 큐를 사용하였다. 생각해보면..

BFS(너비우선탐색)는 DFS와 함께 그래프를 탐색하는 알고리즘 중 하나이다. BFS는 큐로 구현할 수 있다. BFS는 최단거리를 찾는데 많이 이용된다. BFS는 다음과 같은 알고리즘으로 작동한다. 큐에서 하나의 노드를 꺼낸다. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 큐에 삽입한다. 아래와 같은 그래프가 있을 때, 이를 BFS로 탐색한다고 해보자. 노드를 방문할 때 해주어야 할 것이 두가지가 있는데 하나는 방문처리를 하는 것(그래프에선 빨강색으로 표시)이고 또 다른 하나는 큐에 넣어주는 것이다. 시작노드 1번을 큐에 넣고 방문처리한다. 큐에서 노드 1을 뺀다.(뺀 노드는 위쪽에 표시하였다.) 1과 연결된 노드 중 아직 방문하지 않은 2,3 노드를 큐에 넣고 방문처리한다. 큐에서 2를..

그래프란? finite set of vertex(V)와 edge(E)로 이루어진 것 - graph G : (V,E) Edge(간선)란? 집합 E는 VxV의 subset이다. 일종의 relation이라 볼 수 있다. directed graph(digraph) vs. undirected graph 그래프에서 방향성이 중요한지의 여부에 따라 구분 path란? 그래프에서 node의 sequence다. 단, 각 노드를 연결하는 edge가 있어야 함 Connected graph vs. Disconnected graph connected graph : 모든 노드 사이에 path가 존재(disconnected는 그 반대) disconnected graph는 여러 개의 connected component로 구성 그래프에..