💡 문제 설명 비활성 바이러스의 위치가 2로 표시되는데 연구실 바이러스 M개를 활성시킨다는 것은 2로 표시된 위치 중에서 M 개를 선택해서 바이러스를 뿌리겠다는 것이다. 그리고 전체 빈 공간을 바이러스(비활성,활성 포함)로 모두 채우는데 얼마나 걸리는 지를 계산 하는 문제이다. 전형적인 bfs이지만 조합이 한 번 들어갔다는 점에 있어서 아주 살짝 까다로운 느낌을 내려고 한 문제이다. 💡 문제 풀이 먼저 바이러스 정보들을 struct info에 저장하고 이 struct를 벡터로 구성하여 virus정보를 저장한다. 조합을 통해서 바이러스의 활성 상태를 on/off 해 주면서 조합을 구한다. 조합은 중복되지 않는 숫자들을 고르는 것이기 때문에 for (int i = inx ; i < virus.size() ;..

전형적인 DFS문제이다. 위 입력과 같이 인풋이 주어질 때 테트리미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력하는 문제이다. map 을 방문하면서 한 위치를 고정으로 dfs를 4번 돌면 테트리미노가 완성된다. 근데 그중 凸모양(?) 테르리미노는 dfs로 구현이 안되므로 cnt==1일 때 조건을 만들어서 따로 계산한다. 이와 좀 유사한 문제로는 PuyoPuyo(뿌요뿌요)가 있었던 것으로 기억한다. dfs를 돌면서 어떤 도형을 만드는 형태의 문제는 자주 나오는 문제이므로 한 번 풀어보고 감을 잡는 것이 좋다. #define _CRT_SECURE_NO_WARNINGS #include #include int N, M; int map[555][555]; bool visit[555][555]; int dx[4]..

나는 오셀로 게임을 좋아했다. 그리고 못하는 편은 아니라고 생각한다. (하지만 회사 내 어르신에게 여러 번 진 이력이 있다...) 사실 구석 4 모서리를 잘 선점하는 이기는 게임.. ㅋㅋㅋ 문제에서 주어진 오셀로 게임의 설명은 다음과 같다. 무튼 이 문제의 핵심은 흑돌과 백돌을 번갈아가면서 주어진 인풋대로 두는데 각각 돌이 몇개냐를 묻는 문제이다. 방법은 간단하다. 돌을 입력받을 때 마다 find(y_coord, x_coord, wb)를 이용하여 돌을 두고 돌 색을 바꾸면 된다. void find(int Y, int X, int STONE) 함수를 보면 돌을 둔 위치에서 8방향을 체크한다. 돌을 두었다는 것 자체가 먹을 돌이 있다는 얘기이니까 돌을 두었을때 잡아먹을 수 있는 돌이 있는 지는 딱히 신경 쓸..

파란것은 섬이고 하얀것은 바다 그리고 회색의 다리로 섬들을 최소 길이로 이으라는 문제이다. 문제 자체는 이해하기 어렵지 않다. 다리는 직선이어야 하고 길이는 2이상이어야 한다. 그리고 다리는 섬과 섬 사이를 이어야한다. 즉, 다리를 잇는 도중에 다리를 짓는 방향과 다른방향으로 섬이 있다고 해서 섬이 이어졌다고 판단하면 안된다. 그런데 이 문제를 푸는 방법은 좀 생각을 잘 해야 한다. 코드를 보면 좀 복잡 해 보이겠지만 함수의 이름을 최대한 직관적으로 쉽게 지정해 놓았으니 찬찬히 보면서 이해해 보면 좋을 것 같다. 일단 풀이의 알고리즘 순서는 다음과 같다. 1.dfs()를 이용하여 일단 섬의 개수를 구한다. dfs를 이용하여 동서남북 4방향 다 체크하면서 더 이상 갈 곳이 없으면 빠져나와서 섬 개수를 카운..

내가 정말 애정하는 문제 토마토이다. (링크) BFS의 기초를 이해하기에 좋은 문제라고 생각한다. 그리고 여러 코딩테스트(삼전,한화,CosPro 등)을 치루면서 토마토와 유사한 문제들을 자주 봐왔다. 코딩테스트 준비를 시작하는 사람들이라면 토마토 문제는 꼭 한 번 풀어보면 좋겠다. 익은 토마토, 안익은 토마토 개수만 신경쓰면 되고 그 외에는 딱히 어려운 경우는 없다. bfs를 풀 때 가장 중요한 점이 있다. 바로 방문위치이다. queue에서 pop 할 때 방문체크를 하는 것과 queue에 넣어줄 때 방문체크를 하는 것에는 큰 차이가 있다. 꼭 queue에 넣어줄 때 방문체크를 하자 방문체크를 pop 할 때 하는 것은 중복된 값들을 처리하는 경우가 생겨 시간 초과와 같은 에러가 생길 수 있다. 또는 루프에..

문제 자체는 어렵지 않은데 코딩을 할 때 좀 잘 생각해야 하는 문제이다. 시뮬레이션 문제이고 낚시왕이 1번 열의 한 칸 왼쪽에서 오른쪽까지 이동하면 멈추므로 낚시왕의 위치를 기준으로 시뮬레이션을 실행하면 된다. 특히 상어의 위치에 대해서 잘 생각 해야 하는 문제이다. 죽은 상어를 먹고 있지 않은 지 생각해야 한다. 또한, 새로 이동한 상어가 전에 있던 상어의 위치로 옮겨 갈 때(?) 위치 정보가 올바르게 저장되는 지도 잘 따져보자. 나는 개인적으로 어떤 정보를 담고있는 물체(상어)라면 struct를 사용하는 것을 애용한다. 한 번에 모든 정보를 담기 쉽고 접근성이 좋기 때문이다. #define _CRT_SECURE_NO_WARNINGS #define ABS(A,B) A>B? A-B: B-A #includ..