분류 전체보기

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 이 문제는 BFS를 사용해서 해결할 수 있다. 웜 바이러스는 양방향 그래프의 특성을 가진다. 또한 웜 바이러스가 감염 시킬 수 있는 컴퓨터의 최대 수는 N이다. 이러한 점을 통해 반복문으로 통해 N까지 순회하고 현재 컴퓨터에서 웜이 뻗어 나갈 수 있는 컴퓨터를 찾는다. 감염시킬 컴퓨터가 있다면 counter를 증가시킨다. #include #include #include using namespace st..

https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 이 문제는 BFS를 통해 길찾기를 하면 해결할 수 있다. 길찾기를 진행하다 P를 만나면 counter를 증가시킨다. 모든 탐색이 끝나고 counter가 초기 상태와 같다면 TT를 출력한다. #include #include using namespace std; char graph[601][601]; int visited[601][601] = { 0, }; int N, M, counter..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 이 문제는 BFS를 통해 해결할 수 있다. 문제에서 "원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다." 라는 규칙이 있다. 이 규칙을 통해 문제를 풀기 위해 result라는 배열을 생성하고 memset을 통해 -1로 초기화 해주었다. 순회 후 graph가 원래 0인 부분은 0으로..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제는 BFS를 통해 해결할 수 있다. 100칸의 배열을 생성하고 뱀과 사다리와 무관하게 index, value를 통해 배열에 요소를 집어 넣는다. queue의 값이 100이 되면 반복을 멈추고 이동 횟수를 저장한다. 주사위는 1~6까지 있고, 최대 값은 100까지이므로 조건문으로 제어한다. 뱀과 사다리가 있다면 뱀과 사다리 값을 queue에 삽입..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 BFS를 사용해서 해결할 수 있다. 현재 queue에 있는 값이 1이면 연산 횟수를 저장하고 반복을 멈춘다. 값이 3으로 나눠 떨어지거나 2로 나눠 떨어지면 queue에 값을 3이나 2로 나누고 연산 횟수를 저장한다. 또한 값을 1로 뺀 값과 연산 횟수를 저장한다. #include #include #include #include using namespace std; int x, result; queue q; void bfs() { q.push(make_pair(x,0)); while (!q.empty..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이 문제는 BFS를 통해 해결할 수 있다. 탐색을 통해 원하는 좌표에 이동하면, 배열에 이동 값을 삽입한다. 이후 배열을 정렬하여 최소 값을 출력하면 된다. #include #include #include #include using namespace std; int visited[101][101]; int N, M; char graph[101][101]; int dx[] = { 0,0,-1,1 }; int dy[] = { -1,..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이 문제는 DFS를 사용하고, 영역 검사를 하면 해결할 수 있다. #include #include #include #include using namespace std; int visited[26][26]; int dx[] = { 0,0,-1,1 }; int dy[] = { -1,1,0,0 }; vector v; int N, counter = 0, cnt=0; char graph[26][26]; vo..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B) conti..