목록백준 (183)
Study hard
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] bfs알고리즘을 이용하여 풀었다. visited배열에 해당 칸이 출발지로부터 몇번째 칸인지 저장하면서 반복문을 돌리고, 목적지인 (N,M)에 도착하면 bfs함수에서 빠져나오면 된다. 이때 visited[N][M]이 (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소의 칸 수이다. #include #include #include //scanf using namespace std; struct Pos {..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net [풀이] bfs알고리즘을 이용하여 풀었다. riped배열에 해당 좌표의 토마토가 보관 후 며칠이 지났을 때 익었는지 저장했다. 만약 다른 익은 토마토로부터 영향을 받았을 때가 더 빠른 일수라면 그걸로 바꿔줬다. #include #include #include //memset #include //max using namespace std; struct Tomato { int x, ..
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net [풀이] 간단한 bfs알고리즘으로 풀었다. 한 번 bfs를 할 때 방문하지 않은 사각형에 대해 위,아래,왼쪽,오른쪽,대각선으로 연결되어 있는 사각형을 조사하여 한 개의 섬을 모두 조사할 때까지 탐색하였다. bfs를 돌린 횟수가 섬의 개수가 된다. #include #include #include //memset using namespace std; struct Island { int x, y;//육지의 좌..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net [풀이] bfs탐색을 사용하여 풀었다. 그림처럼 단지마다 1,2,3 표시할 필요는 없고, 각 좌표의 상하좌우를 탐색해 이어져 있는 1의 개수를 구하면 된다. #include #include #include //sort #include //scanf using namespace std; struct Pos { int x, y;//Map의 x좌표, y좌표 }; int N; int Map[26][26]..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 www.acmicpc.net [풀이] dfs를 이용하여 풀었다. 다음 학생이 처음 방문하는 학생이면 check[학생번호]를 true로 바꾸어주고, 이미 한 번 방문했던 학생을 다시 방문하게 된다면 Recheck[학생번호]가 false일 경우 거쳐왔던 학생만큼 cnt에 저장한다. (cnt는 프로젝트 팀에 속한 학생들의 수이다) ※dfs마지막에 Recheck[현재 학생번호]를 true로 바꿔줘야 같은 싸이클을 그 싸이클에 속하는 원소..
https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net [풀이] dfs를 사용하여 풀었다. 수열을 구하면서 check[값]을 해당 값이 나올 때마다 +1해주다가 어떤 값이 3번 나오면 반복수열이 되었다는 뜻이므로 함수에서 빠져나온다. ex) 37, 58, 89, 145, 42, 20, 4, 16, 37, 58, 89, 145, 42, 20, 4, 16, 37, ... 이렇게 37이 세번 나와야 반복수열이 되었다는 것을 알 수 있다. check값이 1인 인덱스들이 반복되는 부분을 제외했을 때 수열에 남게되는 수들이다. #include #include //pow u..