24445번: 알고리즘 수업 - 너비 우선 탐색 2

24445번:  알고리즘 수업 - 너비 우선 탐색 2사용 언어: C++ 풀이단순 BFS -> 큐에 넣어서 해당하는 애를 검사할땐 pop하면서 visited = true 해주고 다음 인접한 애를 visit 한 적 없으면 push하고 걔를 검사. 내림차순이므로 sort할때 greater() 넣기.#include #include #include #include using namespace std;vector graph[100001];int visited[100001];int cnt = 1;void bfs(int start){ queue q; q.push(start); visited[start] = cnt++; while (!q.empty()) { int node = q...

24444번: 알고리즘 수업 - 너비 우선 탐색 1

24444번:  알고리즘 수업 - 너비 우선 탐색 1사용 언어: C++ 풀이단순 BFS -> 큐에 넣어서 해당하는 애를 검사할땐 pop하면서 visited = true 해주고 다음 인접한 애를 visit 한 적 없으면 push하고 걔를 검사. 오름차순이므로 그냥 sort.#include #include #include #include using namespace std;vector graph[100001];int visited[100001];int cnt = 1;void bfs(int start){ queue q; q.push(start); visited[start] = cnt++; while (!q.empty()) { int node = q.front(); ..

3190번: 뱀 (BOJ C/C++)

3190번: 뱀 사용 언어: C++ 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 ..

16985번: Maaaaaaaaaze (BOJ C/C++)

16985번: Maaaaaaaaaze 사용 언어: C++ 문제 평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다. 대회의 규칙은 아래와 같다. 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다. 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자..

15683번: 감시 (BOJ C/C++)

15683번: 감시 사용 언어: C++ 이번 문제는 내용이 길고 그림이 많다 보니 직접 백준 페이지를 확인하는 것이 좋을 것 같다. 풀이 저 sight 함수를 재귀로 만들어서 각 재귀마다 ans를 계산하는 풀이를 짜다가 그러면 자칫 잘못하면 재귀가 너무 많이 돌아갈 수 있고 sight 함수를 각 카메라마다 만들어줘야해서 복잡해져서 아래의 brute force 풀이인 for문을 4^Q.size만큼 돌리는 풀이로 바꿨다. 아래의 코드가 queue가 아닌 vector를 쓰면 매번 Q를 Q1으로 초기화 해줘야하는 번거로움이 줄어들 수 있다. #include #define X first #define Y second using namespace std; int board1[10][10]; int board2[10..

3197번: 백조의 호수 (BOJ C/C++)

3197번: 백조의 호수 사용 언어: C++ 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... ....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... ...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X......

9328번: 열쇠 (BOJ C/C++)

9328번: 열쇠 사용 언어: C++ 문제 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다. 각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 ..

11967번: 불켜기

1967번: 불켜기 사용 언어: C++ 문제 농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다. 베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 베시가 불을 켤 수 있는 방의 최대 개수를 구하시오. 입력 첫 번째 줄에는 N(2 ≤ N ≤ 100)과, M(1 ≤ M ≤ ..