728x90 BFS50 [python] 백준 11559 Puyo Puyo https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 문제 해결 문제 상황을 시물레이션으로 구현할 수 있으면 어렵지 않은 문제 첫 행 첫 열부터 하나씩 확인을 해서 이어져 있는 같은 색 뿌요가 4개 이상인지 BFS를 이용해 확인한다. 확인한 점은 다시 확인할 필요가 없으므로 visited를 이용해 구별해서 방문 한 지점은 패스한다. 이어져 있는 같은색 점이 4개 이상이면 터뜨리면서 빈 공간으로 만든다. 모두 한바퀴 확인하면 .. 2023. 11. 23. [python] 백준 1726 로봇 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 문제 해결 BFS를 이용해서 새로운 길을 가면서 최소 거리를 찾는 것은 쉽게 알 수 있다. 그러나 방향을 좌, 우로 90도만큼 트는 것을 생각해야하고 직선으로 1칸부터 3칸까지 갈 수 있다는 것을 생각해야한다. visited에 바라보는 방향까지 포함시켜서 3차원 리스트로 저장을 하도록 한다. 회전은 90도만 가능하므로 동,서일 때는 남,북으로 회전 가능하고 남,북일 대는 동,서 방향으로 회전 가능하다. 중간.. 2023. 11. 22. [python] 백준 1039 교환 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 숫자 안에 서로 다른 두개의 자릿수의 숫자를 바꿔가며 K번 바꾸었을 때 가장 큰 수를 만들 경우를 찾는 문제이다. 따라서 처음에 두 자릿수의 숫자를 바꿔서 가장 큰 수가 나왔다고 K번 바꾸었을 때 가장 큰 수가 만들어진다고 할 수 없다. 즉 거의 모든 경우의 수를 다 계산해야한다. 하지만 예외가 있다. 만약 한 자리의 자릿수가 가장 큰 자릿수, 즉 맨 왼쪽에 있는 수이고 나머지 하나의 자릿 수가 0일 경우 총 숫자의 자리수가 줄어들게 된다. 이런 경우는 예.. 2023. 11. 14. [python] 백준 12851 숨박꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 해결 가장 빠르게 N에서 K로 가는 길을 찾으면 된다. 이 때는 BFS를 이용하는 것이 좋다. 이동 했는데 이미 방문한 적이 있으면 더 빠르게 이동 할 수 있는 방법이 존재하는 것이므로 pass한다. ways를 통해 이동할 수 있는 방법이 여러개면 여러개가 있다는 것을 value 값을 통해 더해주면서 이동할 수 있다. CODE from collection.. 2023. 11. 1. 이전 1 2 3 4 5 ··· 13 다음 728x90
