문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 대표적인 백트래킹 문제인 N-Queen이다. 이 문제는 바킹독님의 영상을 참고하여 풀 수 있었다. 이제 문제를 풀어보자. cur은 행을 의미하고 for문 안의 i는 열을 의미하며 i를 0부터 N - 1까지 모두 돌며 퀸을 배치한다. 0부터 N - 1까지 열을 for문으로 도는 이유는 서로 공격할 수 없게 퀸을 배치하기 위해서는 모든 열에 대해 퀸을 배치해주어야 하기 때문이다. 이때 퀸의 배치에 따라 퀸..
문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net BFS + 구현 문제이다. 삼성 기출 문제라고 하는데 나한테는 같은 티어의 골드4~5문제보다 어려웠다. 단순하게 생각했으면 쉽게 풀었을 것 같은데 너무 어렵게 생각하고 이 문제에 접근해서 그런 것 같다. 풀이 문제의 조건에 따라 BFS를 구현해주었다. 이때 고려할 것은 두가지이다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을..
문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 백준에 있는 불! 문제랑 비슷하다. 물에 대한 BFS와 비버에 대한 BFS를 각각 돌려주어 풀었다. 먼저 물에 대한 BFS를 돌아 물이 차는 시간과 방문 여부를 체크해주었다. 이후에 비버에 대한 BFS를 돌며 비버가 도착할 시간이 물이 차는 시간보다 작아야만 비버가 움직일 수 있기 때문에 조건을 달아주어 만족하는 경우에만 비버가 방문할 수 있게하는 것이 핵심이다. 하지만 예외상황이 발생할 수 있다...
문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 이 문제는 치즈 문제와 다르게 내부 공기/외부 공기의 구분이 없고, 영역의 개수를 구해야하기 때문에 모든 좌표에 대해 BFS를 돌아줘야한다. board의 값이 0인(바다)인 곳에 대해 모두 탐색을 하여 빙산이 있는 곳을 만나면 빙산의 높이를 하나씩 감소시켜주었고, 빙산의 높이가 0이 되면 방문처리를 해주어 이번 탐색에 녹아버린 좌표에 대해서는 BFS를 막아주고 최종적으로 현재 영역..
