2206. 벽 부수고 이동하기 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 오래 걸렸던 문제인데.. 1. 벽이 있는 곳의 위치를 큐에 넣어서. 하나씩 뽑으며 그 부분의 벽을 부시고 매번 bfs를 돌리니 N 벽 부숨 public Pos(int r, int c, int flag) { this.r = r; this.c = c; this.flag = flag; } } static void bfs() { q.offer(new Pos(1, ..
[BJ] 17070.파이프 옮기기1 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net import java.io.*; import java.util.*; // 0306 public class Main_BJ_17070_파이프옮기기1 { static int N, cnt=0; static int[][] map; static int[] dr = {0, 1, 1}; // 가로, 세로, 대각선 순 static int[] dc = {1, 0, 1}..
[BJ] 3109. 빵집
[BJ] 3109. 빵집 www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 이것또한 나를 오래 괴롭혔던 백트래킹 문제다.. 가지치기 1번을 하는 이유를 이해하지 못했는데 하나하나 그림을 그려보다 이해했다. 역시 이해 안될 때는 해보는게 최고다. 1. 가지치기1 : dfs 탐색을 하다가 마지막 열까지 간다면, true를 반환하거나 false를 반환하는 작업을 통하여 더 이상의 탐색을 멈추는 가지치기를 수행하여야 한다. 예를 들어, d = 0에서 dfs 탐색을 하여 파이프 놓기에..
[BJ] 17406. 배열 돌리기 4
17406. 배열 돌리기 4 www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 배열 회전 + 순열 까지 모두 사용해야 하는 문제였다. 명령어를 수행하는 순서에 따라 배열값이 다르게 된다. 명령어를 수행하는 순서를 순열로 구한 다음, 순열 순서대로 실행해보며 최소값을 구해야 한다. 이때, 배열을 복사하여 사용하지 않고 초기 배열을 가지고 연산을 수행하게 된다면, 다음 순열 순서대로 rotate할 때 바뀐 배열로 계산하게 된다. 따라..
[BJ] 17135: 캐슬 디펜스
[BJ] 17135: 캐슬 디펜스 www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 나를 오랜 기간 괴롭게 했던 이 문제.. 1. 3명의 궁수들은 동시에 같은 적을 노릴 수 있다. 따라서 궁수 한명 씩, 가장 가까운 적을 찾았다고 해서 바로 죽이면 안된다. 그러면 다음 궁수가 같은 적을 노리지 않고 다음 적을 노리게 되기 때문이다. 3명의 궁수 위치 기준에서 가장 가까운 적들을 배열에 넣어놓고, 3명의 궁수에 대한 검사가 모두 끝나면 한꺼번에 죽인다. 2. 궁수와 적의 ..
[BJ] 7576. 토마토
7576. 토마토 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 토마토의 위치를 큐에 넣어서, 토마토 위치부터 bfs 시작하기 import java.io.*; import java.util.*; // 0302 public class Main_BJ_7576_토마토 { static int N, M, map[][], dist[][]; static Queue q; static int[] dr = {-1, 1, 0, 0}; static int[] d..
[BJ] 9663. N-Queen
[BJ] 9663. N-Queen www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 문제!!! 1. 퀸들은 같은 행, 같은 열, 같은 대각선에 올 수 없다. 이때 같은 대각선에 올 수 없다는 말을, 바로 위의 행과 대각선 위치가 아니면 된다고 생각해서 푸는데 오래 걸렸다. 하나의 행 / 하나의 열 / 하나의 대각선에는 하나의 퀸만 올 수 있다고 생각하고 풀어야 한다. 2. cols 배열 -> idx행, cols[idx] 열에 퀸이 놓여있다는 뜻이다. import ja..
[BJ] 8320. 직사각형을 만드는 방법 www.acmicpc.net/problem/8320 8320번: 직사각형을 만드는 방법 상근이는 변의 길이가 1인 정사각형 n개를 가지고 있다. 이 정사각형을 이용해서 만들 수 있는 직사각형의 개수는 총 몇 개일까? 두 직사각형 A와 B가 있을 때, A를 이동, 회전시켜서 B를 만들 수 www.acmicpc.net 직사각형의 넓이는 가로 * 세로인 것 처럼 직사각형 하나에 들어있는, 길이가 1인 정사각형 개수는 가로 개수 * 세로 개수 임을 생각하면 쉽게 풀 수 있다. 이걸 생각 못해서 오래 걸렸다 import java.io.*; import java.util.*; // 210225 public class Main_BJ_8320_직사각형을만드는방법 { stati..