안녕

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는 블럭의 그룹을 적어놓은 리스트임 참고로 한 구역에 블럭이 하나만 있는 경우를 대비해서, 시작과 동시에 블럭에 그룹 번호를 부여하였음 다만..

0. 문제 링크 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 1. 풀이 방법 에라토스테네스의 체로 소수들을 먼저 찾아놓음 그리고 각 자리수를 추출해서 풀었음 1, 10, 100의 자리 숫자는 0이 되어도 상관이 없지만, 1000의 자리는 0이 되면 안 됨 따라서 반복을 1, 10, 100은 합쳐서 27번, 1000의 자리는 8번 반복해야 함 아무튼 만약 1의 자리가 3이라면 -2, -1, 1, 2, 3, 4, 5, 6 이렇게 원래 숫자에 더하도록 구..

0. 문제 링크 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 1. 풀이 방법 단순 BFS를 하면 되는데, 추가로 내가 이미 방문한 곳보다 말을 적게 탔을 경우도 생각해봐야 한다. 또한 임계치보다 말을 적게 탔을 경우에는 말을 추가로 탈 수 있도록 처리함 아래에서 check 변수는 어느 지점까지 말을 탄 횟수이고, cur_k는 현재 내가 말을 탄 횟수 그 외엔 특별한 점 없음 2. 코드 import sys from collections im..

1월 달은 너무 바빴어요 (핑계 아님) 다시 짬짬히 글 쓰려구요 .. 자세한건 나중에 쓸게요