안녕

0. 문제 링크 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 1. 풀이 방법 우선은 어떤 조건이 우선순위인지 생각을 했다. 최단거리를 출력하는 것과 벽을 몇 개 부쉈는지가 중요한 조건이라고 생각했다. BFS 특성상 먼저 도착하는 것이 항상 최단거리이므로 벽을 조건으로 생각을 했다. 따라서 visited 배열을 k + 1로 초기화를 했다. 그렇게 하고, 방문 표시를 현재까지 부순 벽의 횟수를 저장했다. 만약..

0. 문제 링크 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 1. 풀이 방법 우선 0이 있을 때, 해당 0과 인접한 0을 모두 읽었다. 당연히 방문 표시는 했고, 이때 방문한 0의 위치를 모두 좌표로 저장했다. 그리고 나서 다시 방문하면서 그룹 번호와 개수를 부여했다. 그룹 번호는 참고로 복소수의 허수 부분으로 대체했다. 이렇게 하면 특정 위치의 0에 대해서, 이 0이 속한 그룹의 0의 개수와 그룹 번호도 알 수 있다..

0. 문제 링크 https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 1. 풀이 방법 방문 표시를 하면서, deque에 넣고, BFS를 했다. 크게 어렵지는 않았음 2. 코드 from collections import deque n = int(input()) r1, c1, r2, c2 = map(int, input().split()) dir = [(-2, -1), (-2,..

0. 문제 링크 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 1. 풀이 방법 맨 처음에는 리스트를 인덱스에 해당하는 값으로 초기화한다. 이후 뱀 혹은 사다리의 목적지에 해당하는 곳에는 목적지의 좌표로 값을 넣는다. 그리고 deque에 첫 번째 칸과 횟수(0)를 복소수로 만들어서 넣고 시작한다. deque에서 값을 뺀다. 1~6까지 주사위를 굴려본다. 만약 주사위를 굴린 다음 위치가 100보다 ..

0. 문제 링크 https://www.acmicpc.net/problem/12906 12906번: 새로운 하노이 탑 첫째 줄에 막대 A에 놓여져 있는 원판의 개수와 막대 A의 상태, 둘째 줄에 막대 B에 놓여져 있는 원판의 개수와 막대 B의 상태, 셋째 줄에 막대 C에 놓여져 있는 원판의 개수와 막대 C의 상태가 주 www.acmicpc.net 1. 풀이 방법 이 문제의 관건은 어떻게 방문 처리를 할 것이냐 인듯하다.. 편의상 1번, 2번, 3번 스택이라고 얘기하겠다. 나는 처음에 1번, 2번, 3번 따로 생각해서 중복 처리를 했는데, 이러면 문제가 생긴다. 따라서 1번, 2번, 3번을 합쳐서 방문 처리를 해야 한다. 예를 들면 1번에 A, 2번에 BC, 3번에 A 가 있으면 A.BC.A를 방문했다고 처..

0. 문제 링크 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. 풀이 방법 우선 특정 좌표를 기준으로 같은 색깔인 그룹을 만든다. 이건 적록색약과 일반인 두 개로 나눠서 하면 되고, 그룹을 만들다가 같은 색이 아닌 색깔을 만나면 check 변수에다가 -1을 집어 넣는다. check가 0인 곳은 탐색할 필요가 있는 곳으로 0이 아닌 좌표는 탐색할 필요가 없다. 이미 그룹화 되어 있으므로 탐색할 필요가 없는 것 아무튼 2중 for lo..

0. 문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 1. 풀이 방법 + 23.02.04에서 문제를 다시 채점하니 시간 초과가 났습니다.ㅜ 이 문제를 보고 맨 처음 떠오른 생각은 다익스트라였다. 최단 거리를 먼저 찾고, 최단 루트에서 방향이 바뀌는 부분이 거울이니까 그만큼 하면 되겠지 라는 생각을 했다. 하지만 이런 생각은 틀린게, 최단 루트가 최소 거울 개수를 보장하지 않는다! 아래 예시를 보자.. 중간으로 가는 루트가 가..

0. 문제 링크 https://www.acmicpc.net/problem/5014 1. 풀이 방법 BFS를 사용해서 푸는 문제 현재 층과 목적 층이 같다면 끝 그게 아니라면 U만큼 위로 가거나, D만큼 아래로 가면 됨 범위를 벗어나면 안 되고, 이미 방문한 곳을 또 방문하면 안 됨 2. 코드 from collections import deque F, S, G, U, D = map(int, input().split()) if S == G: print(0), exit(0) # 현재 층과 목적지가 같다면 끝 board = [*range(0, F + 1)] board[S] = 0 dy = [U, -D] # U만큼 위로 가거나, D만큼 아래로 가는 것 dq = deque([[S, 0]]) while dq: y, ..

0. 문제 링크 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 1. 풀이 방법 TSP로 문제를 풀었음 BFS를 사용하여 청소기와 쓰레기들의 거리, 쓰레기들 사이의 거리를 모두 파악함 이후 순열을 사용하여 청소기와 쓰레기를 한 줄로 잇는 최단 거리를 파악함 그러나 효율성이 낮으므로, 이 방법 대신 다른 방법을 사용하면 좋을 듯 다른 방법으로는 각 쓰레기에 먼저 방문하는 노드의 경로들을 저장해서 처리하는 방법이 있음 이때 중복은 넣지 않고, (왜냐면 BF..

0. 문제 링크 https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 1. 풀이 방법 각 구역을 그룹화 한 다음에 처리함 또한 인접한 그룹 번호도 넣어서 최댓값을 찾음 비트마스킹을 써서 벽의 위치를 파악함 cnt는 특정 구역의 블록 갯수이고, adj는 특정 구역의 인접한 구역의 인덱스를 넣어놓았음 check는 블럭의 그룹을 적어놓은 리스트임 참고로 한 구역에 블럭이 하나만 있는 경우를 대비해서, 시작과 동시에 블럭에 그룹 번호를 부여하였음 다만..