본문 바로가기
728x90

그래프64

[python] 백준 2638 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 문제 해결 전형적으로 그래프 안에서 이동해서 모두 공기가 되는데 까지 걸리는 시간이므로 bfs를 사용하는 것이 좋을 것이다. 그런데 문제는 치즈를 중심으로 보는 것이 아니라 공기를 중심으로 언제 녹는 벽(치즈)가 다 없어지는지 확인하는 문제이다. 따라서 While 반복문을 통해 시간을 측정하면서 언제 장애물을 안만나는지 확인하면 되는문제 BFS로 공기를 이동시키면서 어느 치즈지역이 공.. 2023. 12. 21.
[python] 백준 1981 배열에서 이동 https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 해결 (1,1)에서 (n,n)까지 가는데 거쳐간 수들 중 최솟값과 최댓값 차이를 구하는 문제 이동하면서 최솟값과 최댓값을 변경해가며 저장하고 갈 수도 있을 것 같은데 그러면 que안에 너무 많은 데이터가 저장이 되어 메모리 제한에 걸린다. 따라서 최솟값과 최댓값을 고정값으로 가져가며 그 안에 수들이 통과하여 이동할 수 있는지 확인해가는 식으로 bfs를 이용할 수 있다는.. 2023. 12. 4.
[python] 백준 2234 성곽 https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 문제 해결 우선 숫자에 따라 벽이 존재유무를 확인할 수 있다. 남: 8, 동:4, 북:2, 서:1인 만큼 bfs의 이동방향도 남, 동, 북, 서 순서대로 해서 값을 비교해서 벽의 존재유무를 알 수 있다. 벽이 존재하지 않으면 일반 bfs와 다를바가 없다. 다만 각 영역에 대한 기록을 해야하므로 room_info를 통해 group_num과 땅 사이즈를 위치마다 기록을 한다. 하나의 벽을 허물 .. 2023. 12. 3.
[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.
728x90