본문 바로가기

알고리즘/구현7

[Python] 백준 1018 체스판 다시 칠하기 🧑‍💻 [Python] 백준 1018 체스판 다시 칠하기 Silver 4 - 완전 탐색 코드 N, M = map(int, input().split()) board = [list(input()) for _ in range(N)] def chess(i, j): global result change_1,change_2 = 0, 0 for row in range(8): for column in range(8): if (row + column) % 2 == 0 and board[i + row][j + column] == "B": change_1 += 1 elif (row + column) % 2 == 1 and board[i + row][j + column] == "W": change_1 += 1 if (row .. 2023. 3. 24.
[Python] 백준 15683 감시 🧑‍💻 [Python] 백준 15683 감시 Gold 4 - 구현 DFS를 하는 것인데, CCTV를 DFS 하는 것이다 CCTV 가 3개가 있으면 3개의 감시하는 방향을 DFS로 탐색을 한다 탐색한 방향에다가 '#'을 넣는다 0의 개수를 센다음, 제일 작은 수를 찾는 것 지도가 주어진다고, DFS를 지도에 할 생각부터 하지 말자 ㅜ.ㅜ 코드 from copy import deepcopy N, M = map(int, input().split()) dr,dc = [-1, 0, 1, 0], [0, 1, 0, -1] direction = [[], [[0], [1], [2], [3]], [(0, 2), (1, 3)], [(0, 1), (1, 2), (2, 3), (3, 0)], [(0, 1, 2), (1, 2, .. 2023. 3. 20.
[Python] 백준 14719 빗물 🧑‍💻 [Python] 백준 14719 빗물 Gold 4 - 구현 입력 값 M, N = 4, 8 3 1 2 3 4 1 1 2 i left right min(max(left), max(right)) block[i] water 1 3 2, 3, 4, 1, 1, 2 3 1 2 2 3, 1 3, 4, 1, 1, 2 3 2 3 3 3, 1, 2 4, 1, 1, 2 3 3 3 4 3, 1, 2, 3 1, 1, 2 3 4 3 5 3, 1, 2, 3, 4 1, 2 2 1 4 6 3, 1, 2, 3, 4, 1 2 2 1 5 left, right 는 현재의 인덱스 기준으로 왼쪽과 오른쪽에, 더 큰 지역이 있는지 보는 것이다 이것을 통해서 물이 고이는지 안 고이는지 알 수 있다 min(max(left), max(right).. 2023. 3. 15.
[Python] 백준 15686 치킨 배 🧑‍💻 [Python] 백준 15686 치킨 배 Gold 5 - 구현 치킨과 집의 좌표들을 각 chicken과 home 리스트에 넣었다 일단 최대 치킨의 수를 입력 받으니깐, 치킨의 좌표를 combinations를 통해 순열을 찾는다 그리고 집의 기준으로 치킨 좌표들과 비교해서, 제일 가까운 거리를 찾으면 된다 코드 from itertools import combinations N, M = map(int, input().split()) city = [list(map(int, input().split())) for _ in range(N)] chicken, home = [], [] result = N ** N for i in range(N): for j in range(N): if city[i][j] ==.. 2023. 3. 14.
[Python] 백준 14502 연구소 🧑‍💻 [Python] 백준 14502 연구소 Gold 4 - 구현 from copy import deepcopy 깊은 복사를 하는 것이다 깊은 복사를 하면, 완전 다른 인스턴스가 만들어진다 (남남이 되는 것) combinations 을 사용해서 배치할 벽들의 좌표를 구했다 empty_space 리스트에 비어 있는 공간들의 좌표들을 넣었다 비어있는 공간들의 좌표의 순열을 통해 벽들을 배치하고, 바이러스가 얼마나 퍼지는지 구하는 것 for empty in combinations(empty_space, 3): 비어있는 공간들의 좌표 3개를 통해 벽들을 배치해준다 BFS를 하는데, BFS는 마지막에 퍼진 바이러스의 개수를 반환해준다 퍼진 바이러스의 개수의 최소값을 구하면 된다 코드 디테일 queue = deq.. 2023. 3. 14.
[Python] 백준 3107 IPv6 🧑‍💻 [Python] 백준 3107 IPv6 Gold 5 - 구현 이 문제는 IPv6를 고려해서, 상황들을 생각해서 코드를 짜면 되는 것이다 특히 ::를 집중적으로 생각해야 한다 :: 만 없었다면 그냥 0만 채우면 되는 문제 예) 25:09:1985:aa:091:4846:374:bb 같은 경우 그냥 0025:0009:1985:00aa:0091:4846:0374:00bb으로 바꿔주면 된다 그래서 입력을 먼저 받을 때에 : 기준으로 나눠서 리스트에 넣는다 그리고 그 리스트 안에 있는 요소들을 순회한다 만약 중간에 ::가 있으면, 리스트에는 ''으로 반환되어 있을 것이다 리스트 길이가 8이면 그대로 0만 채워 넣으면 된다 하지만 리스트 길이가 8이 아니면, ::를 채워 넣어줘야 한다 리스트 길이를 8로 맞출.. 2023. 3. 12.
[Python] 백준 1913 달팽이 🧑‍💻 [Python] 백준 1913 달팽이 Silver 3 - 구현 무조건 matrix[0][0]은 N * N 이다 시작을 N * N으로 하고, 내려가면서 -1 을 한다 만약에 다음 좌표가 0이 아니거나, 행렬을 나가게 된다면 왼쪽으로 90도를 돌아서 앞으로 가면서 -1을 하면 된다 이것을 좌표의 값이 1이 될때까지 진행을 한다 코드 N = int(input()) M = int(input()) matrix = [[0] * N for _ in range(N)] num, i, j = N * N, 0, 0 ans_row, ans_column = 0, 0 while num > 0: # 아래로 내려가기 while i < N and matrix[i][j] == 0: if num == M: ans_row, ans_.. 2023. 3. 4.

티스토리툴바