안녕

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..