본문 바로가기

Algorithm/Graph188

[파이썬] 백준 2573 : 빙산 (골드4) [파이썬] 백준 2573 : 빙산 (골드4) 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 풀이 0. 방향성 생각 주어진 배열의 크기가 크고 시간이 지남에 따라 지속적으로 빙산의 개수를 체크해야한다. DFS보다는 BFS가 시간적으로 이득일 것 같다. 또한 빙산에 인접한 바다의 개수를 세면서 빙산을 녹이면 빙산이 0이 될 경우에 오류가 발생할 수 있어서 추가적인 리스트를 만들어준다. 1. 입력받기 from collections import deque import sys input = sys.stdi.. 2023. 5. 14.
[파이썬] 백준 2589 : 보물섬 (골드5) [파이썬] 백준 2589 : 보물섬 (골드5) 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 문제 풀이 0. 방향성 생각 최장거리 문제라 BFS로 방향성을 잡는다. 하지만 군집 내에 점마다 거리가 달라지므로 최장거리를 찾으려면 모든 점을 탐색해야한다. (더 좋은 방법은 모르겠다) 1. 입력 받기 from collections import deque import sys input = sys.stdin.readline h,w = map(int,input().split()) arr = [] for i in range.. 2023. 5. 13.
[파이썬] 백준 7576,7579 : 토마토 (골드5) [파이썬] 백준 7576 ,7579: 토마토 (골드5) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 풀이 0. 방향성 생각 최단거리 문제라서 BFS로 접근. 마지막 출력하는 부분만 조심하면 별 다른 조건도 없다. 1. 입력 import sys from collections import deque input = sys.stdin.readline w,h = map(int,input().split()) arr = [] q = deque() for i in range(h): s = list(.. 2023. 5. 10.
[파이썬] 백준 10026 : 적록색약 (골드5) [파이썬] 백준 10026 : 적록색약 (골드5) 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 오답 n = int(input()) arr= [] for i in range(n): arr.append(list(input()) def dfs(x,y,color): if x=n : return 0 if arr[y][x] == color: arr[y][x] = 0 return 1+dfs(x-1,y,color)+dfs(x+1,y,color)+dfs(x,y-1,color)+dfs(x,y+1,color) re.. 2023. 5. 10.

티스토리툴바