https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net [풀이] BFS 유형의 문제입니다. BFS를 기본적으로 연습할 수 있는 문제라고 생각합니다. 시작 위치와 도착 위치를 배열에 받아 도착 위치에 가기까지 횟수를 더합니다. 도착 위치의 x,y 좌표값이 동일하다면, bfs 메소드가 종료되고 count 변수를 출력합니다. [코드] import java.io.BufferedReader; import java.io.IOException; import java..
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net [풀이] 정렬을 이용한 문제였습니다. 기존 배열은 정렬 시킬 경우, 이후 기존 배열의 각 값의 위치를 알 수 없으므로 clone() 메소드를 통해 깊은 복사를 합니다. Map의 key는 좌표값을, value는 좌표값에 대한 최소 인덱스를 저장합니다. 만약, Map에 이미 있는 값이라면 무시하고, 없는 값이라면 좌표값과 인덱스를 저장하며 하나 증가시..
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 완전탐색 유형의 문제입니다. solve 메소드를 통해 재귀적으로 탐색합니다. 여기서 check 메소드를 통해 현재 위치에 놓을 수 있는지 없는지를 판단합니다. 현재 행의 위치에 놓을 수 없는지, 대각선에 이미 있는지 등을 확인해서 값을 반환합니다. 열의 차와 행의 차가 같을 경우가 대각선에 놓여 있는 경우입니다. [코드] import java.io.BufferedReader; import java.io...
https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net [풀이] 구현 및 규칙과 관련한 문제였습니다. 입력받는 수가 어떠한 범위에 있는지를 토대로 몇층에 있는지 계산하여야 합니다. 1이 입력되면 1개의 방을 지난다고 출력해야 합니다. 2부터 7까지는 2층에 있으며 2층에는 총 6개의 벌집이 있습니다. 8부터 19까지는 3층에 있으며 3층에는 총 12개의 벌집이 있습니다. 20부터 37까지는 4층에 있으며 4층에는 총 18개의 벌집이 있습니다. 38부터 61까지..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [풀이] dfs 메소드는 벽을 3개 세우는 것을 재귀적으로 구현한 부분입니다. bfs 메소드는 바이러스가 퍼지는 것을 구현한 부분입니다. check 메소드는 안전한 영역의 최대값을 구현한 부분입니다. 벽을 3개 세우고 바이러스가 퍼졌을 때 안전한 영역의 개수를 구하므로 dfs 메소드내에 bfs 메소드, bfs 메소드 내에 check 메소드가 위치합니다. 즉, dfs 메소드에서 벽을 다 세웠을 경우, bfs 메..
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net [풀이] 완전 탐색 유형의 문제입니다. 높이는 1이상 100이하의 정수이므로 for문으로 copyArr에 높이 이하일경우 0, 초과일 경우 1을 입력합니다. copyArr에 매번 넣을 때마다, 방문하지 않은 곳과 안전한 영역을 체크하며 solve() 메소드를 호출합니다. solve() 메소드는 dfs를 이용한 메소드입니다. 영역의 개수를 셀 때, solve() 메소드가 호출된 개수가 곧 영역의 개수입니다..
