bfs4

• 

  그래프(Graph) : 너비우선탐색(BFS) & 깊이우선탐색(DFS) 그래프- 그래프란 노드(Node)와 간선(Edge)로 이루어진 연결 구조입니다.- 노드는 점을 의미하고, 간선은 노드간 연결되어 있는 선을 의미합니다.  가중 그래프- 가중 그래프는 간선에 숫자를 부여해서 무게나 비용을 의미하게 만든 그래프입니다. 방향 그래프- 방향 그래프는 간선에 방향을 부여해서 특정 방향으로만 이동할 수 있는 그래프입니다.- 방향 그래프가 아닌 그래프는 양방향그래프라고 생각하면 됩니다.- 가중 그래프처럼 비용, 무게를 부여할 수 있습니다.  너비 우선 탐색 (Breadth First Search)- 시작점에서부터 목표점까지 갈 수 있는지 탐색하는 알고리즘입니다.- 시작점에서 가까운 곳 부터 방문하는 알고리즘입니다.- 선입선출 구조로 Queue(큐)를 주로 이용합니다. ex) A에서 .. CS 지식/자료구조_알고리즘 2025. 1. 13.

• 

  BJ S3 2606 바이러스 -Java [문제링크]https://www.acmicpc.net/problem/2606[문제]신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보.. 알고리즘/DFS_BFS 2024. 10. 9.

• BJ S2 21736 헌내기는 친구가 필요해 - Java [문제링크]https://www.acmicpc.net/problem/21736[문제]2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 도연이가 다니는 대학의 캠퍼스는 N×M$N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x$x$, y$y$)에 있다면 이동할 수 있는 곳은 (x+1$x+1$, y$y$), (x$x$, y+1$y+1$), (x−1$x-1$, y$y$), (x$x$, y−1$y-1$)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날.. 알고리즘/DFS_BFS 2024. 10. 2.

• 

  BJ G5 7569 토마토 - Java [문제링크]https://www.acmicpc.net/problem/7569 [문제]철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 .. 알고리즘/DFS_BFS 2024. 10. 1.