본문 바로가기
728x90

그래프64

[python] 백준 6593 상범 빌딩 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 문제해결 BFS의 전형적인 문제이지만 3차원으로 확장했다는 것이 다르다. CODE from collections import deque import sys input = sys.stdin.readline INF = sys.maxsize def bfs(z,x,y): global answer que = deque() que.append((z,x,y,0)) visited = [[[-1 for _ in ran.. 2023. 4. 26.
[python] 백준 17471 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 해결 삼성 A형 기출문제 딱 봐도 완전탐색 문제이다.(2 ≤ N ≤ 10, 1 ≤ 구역의 인구 수 ≤ 100) 문제는 combination을 사용하여 모든 경우의 수를 다 고민을 해야하나인데... 맞다. 1개부터 n//2 개까지 선거구를 뽑은 다음 다 연결 되었는지 확인하고 나머지 선거구끼리도 모두 연결되었는지 확인해야한다. 모두 연결이 되면 두 집단의 인구 차이를 이전과 비교해서 작은 값을 저장한다. 삼성은 i.. 2023. 4. 26.
[python] 백준 2589 보물섬 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제 해결 전형적인 bfs문제 그러나 시작점을 기준점으로 하여 모든 경우의 시작점에서 다 경우의 수를 계산해봐야 하는지 의문이 들었다. 50*50 지점이라 계산이 되겠지만 사실 다른 방법이 생각이 안났다. python3버전은 시간초과가 뜨고 pypy3버전은 통과를 한다. 시간 문제에 대해서는 더 고민해봐야겠다. CODE from collections import deque import sys inpu.. 2023. 4. 22.
[python] 백준 1941 소문난 칠공주 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제해결 조건이 4가지를 만족해야하므로 차례대로 만족시킬 수 있는 방법이 뭔지 생각해본다. 1번과2번조건을 묶고 3번과 4번 조건을 묶으면 좋다. 7명의 여학생으로 구성되어있어야하므로 depth=7인 dfs를 사용하면 좋을 것 같다. (게다가 가로 또는 세로로 인접해 있어야하므로 dfs로 이동하는 것은 좋다.) 임도연파가 4명 이상이면 안되는 것이기 때문에 중간에 그만두고 다른 것을 찾도록 한다. b.. 2023. 4. 18.
728x90