두부의 코딩일기

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net ✅ 골드 Ⅱ 🔶 풀이 베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오. (1, 1) 부터 상, 하, 좌, 우로 움직일 수 있고 불이 켜져 있는 곳만 이동할 수 있다. 출력에서 조심해야 할 건 베시가 이동할 수 있는 방의 개수가 아니라 불을 켤 수 있는 방의 최대 개수다. 질문 게시판 보니까 실수하시는 분들이 정말 많았다. 상하좌우로 이동하..

https://www.acmicpc.net/problem/1175 1175번: 배달 어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사 www.acmicpc.net ✅ 골드 Ⅰ 🔶 풀이 배달해야하는 곳은 총 2곳이고, 같은 방향으로 연속해서 이동할 수 없음. 단순 bfs를 돌리면서 신경써야할 건 총 두 가지였다. 1️⃣ 같은 방향으로 연속해서 이동할 수 없다. 2️⃣ 현재까지 배달한 곳 1️⃣번의 경우에는 아래와 같은 방법으로 쉽게 해결할 수 있다. // 같은 방향으로 연속해서 움직일 수 없음 if (cur.d == d) continue; 2️⃣번의 경우에 필자는 배달해..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net ✅ 골드 Ⅴ 🔶 풀이 최소 한 개의 모음과 두 개의 자음으로 구성된 길이 L의 암호를 출력하라. 백트래킹으로 풀어야 된다. 해당 문제에서는 알파벳이 증가하는 순서로 배열되었을 것이라고 한다. 정렬은 필수다. 우선, 이미 선택한 알파벳보다 큰 알파벳을 선택해서 임의의 L 길이를 가진 암호를 만든다. L 길이가 완성됐다면 최소 모음 1개, 자음 2개를 가지고 있는지 판단해 준다. public static ..

https://www.acmicpc.net/problem/2412 2412번: 암벽 등반 어떤 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동 www.acmicpc.net 🔶 풀이 BFS로 충분히 해결할 수 있는 문제. (0, 0)에서 시작해서 (x, T)까지 올라가면 된다. 우선 입력값을 y값을 기준으로 배열을 만들어서 입력해줬다. rock = new ArrayList[200001]; // T의 최대값: 2,000,000 for (int i=0; i

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 🔶 풀이 외부 공기와 접촉하고 있는 변이 2개 이상인 치즈는 1시간 뒤에 녹는다. "몇 시간 뒤에 치즈가 다 녹아서 없어질까?" 처음엔 치즈를 기준으로 bfs를 돌릴 생각으로 풀다가 시간을 많이 소비했다. 치즈가 아닌 공기를 기준으로 bfs를 돌려야 정답을 구할 수 있는데 문제는 외부 공기와 내부 공기가 나누어져 있다. (0, 0)부터 시작해서 bfs를 돌려준다. 내부 공기와 구분을 ..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 입력하는 과정에서 가로선 정보를 2차원 배열 map[][]에 3가지 경우로 나눠서 입력해줬다. 0: 해당 칸에는 가로선이 없음 1: 해당 칸에서 오른쪽으로 연결되는 선이 존재함 2: 해당 칸에서 왼쪽으로 연결되는 선이 존재함 해당 문제는 3개 이하의 가로선을 만들어서 i번에서 출발하면 i번으로 도착하게 만드는 문제다. 3개 이하의 가로선을 만들어야하기 때문에 dfs를 돌릴 때 limit 함..

https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 처음엔 완전 탐색으로 접근했다가 메모리 초과가 발생했다. 2중 for문을 이용해서 모든 경우의 수를 변경해준다. 이 과정에서 visited[number][cnt] 2차원 배열로 자리를 바꾼 후에 생기는 중복된 수를 제거했다. 중복된 수를 제거할 때는 변경 횟수도 중요하다. 변경된 숫자가 같더라도 1번 변경했을 때 나온 A와 2번 변경했을 때 나오는 B는 전혀 다르다. 그렇기 때문에 변경 횟수도 방문 여부를 체크해줄 때 꼭 필요하다. for (int i=0; i

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 이번 문제는 조건이 많아서 고민할 게 많았다. 구동 순서는 아래와 같다. 택시 위치로부터 가장 가까운 손님을 찾는다. (findPerson) - bfs 가까운 손님의 목적지까지 이동 (goTaxi) - bfs 위 내용을 반복한다. 1. 택시 위치로부터 가장 가까운 손님을 찾는다. public static void findPerson(int x, int ..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 기본적인 bfs 에서 말이 이동할 수 있는 경로만 신경써주면 된다. 말처럼 이동할 수 있는 기회는 K번으로 횟수가 제한되어있으며 벽을 넘을 수 있다. 시작점 (0, 0) 으로 출발해서 (w, h) 까지 최소한의 횟수로 도착하면 된다. 원숭이 상태와 말 상태일 때를 구분해서 돌려주면 쉽게 해결할 수 있다. 1. 원숭이 상태일 경우 1) 이미 방문을 했는지 여부 판단 (visit..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 기본적인 bfs 에 간단한 조건만 추가하면 해결 할 수 있는 문제이다. 시작점 (0, 0) 에서 도착점 (N, M) 으로 갈 수 있는 최단 거리를 구하면 된다. Position 클래스를 생성할 때 x 좌표, y 좌표, 거리, 벽을 부셨는지 여부를 함께 저장할 수 있도록 선언한다. public static class Position { int x; // x 좌표 int..