" 백준 1926번 그림 문제 파이썬 " " 💡 문제 해결 아이디어 " 1926번 그림 문제는 0과 1로 이루어진 그래프에서 상하좌우가 1로 연결된 그림을 찾아 그 갯수와 그 그림들 중 가장 넓은 넓이를 출력하는 문제이다. for문을 통해 그래프의 0,0 ~ n-1,m-1 까지 전체를 탐색하며 값이 1인 지점을 찾을 때마다 cnt +=1 을 한다. 그리고 값이 1인 지점의 x,y좌표를 bfs로 탐색하여 그 지점에 연결되어 있는 1들을 모두 0으로 변경하며 1이 0으로 변경되는 횟수를 area(넓이) 변수에 +1 해주고 더이상 연결된 1이 없다면 area 변수의 값을 return한다. return받은 area변수는 이전에 서칭한 가장 넓었던 그림의 면적(maxArea 변수)와 비교하여 더 큰 값을 다시 m..
백준 1303번 전쟁 - 전투 문제 이 문제는 전쟁터에서 뭉쳐있는 병사들을 찾아내어 그들의 전투력을 계산하는 문제로 예제 입력을 통해 알 수 있듯이 완전 탐색을 이용해 풀 수 있는 문제이다. 본인은 BFS를 사용하여 문제를 해결하였다. " 💡 문제 해결 아이디어 " 문제는 말했다시피 BFS를 사용하여 해결하였다. 우선 bpower, wpower 변수를 0으로 미리 초기화시켜둔다. 그리고 입력받은 문자열(BWWWB.. 등)은 n개의 문자로 쪼개어 그래프에 한 줄씩 list단위로 저장하여 n X m 형태의 2차원 배열을 생성한다. 그래프 생성이 완료되면 그래프의 0,0부터 m-1,n-1 까지 탐색하면서 B또는 W를 찾는데 만약 해당 좌표의 값이 'B' 또는 'W'라면 bfs를 통해 뭉쳐있는 같은 팀 병사를 ..
백준 1260번 음식물 피하기 문제 "💡 문제 해결 아이디어 " 해당 문제는 BFS를 통해 해결할 수 있었다. 음식물 피하기는 어떤 가장 큰 음식물 쓰레기의 사이즈를 구하는 문제이다. 음식물 쓰레기는 근처(상,하,좌,우)에 붙어있으면 더 큰 크기로 변하는데 가장 많이 붙어있는 음식물 쓰레기의 범위를 구하면 되는 문제이다. 이러한 힌트가 문제에 주어지는데 이처럼 그래프를 형성하여 BFS를 통해 가장 많이 연결되어있는 '#'의 count를 구해 답을 유추했다. 0,0 ~ n-1,m-1 범위를 이중 반복문으로 모두 방문하며 그래프의 값이 '#'이면 bfs를 통해 연결되어있는 음식물 쓰레기의 갯수를 구해 return한다. 여기서 return 받은 값들 중 가장 큰 값이 답이기 때문에 max라는 변수를 -1로 초..
백준 1260번 DFS와 BFS DFS와 BFS를 사용하여 정렬한 값을 출력하는 문제이다. 💡 문제 해결 아이디어 정답 비율이 낮아 재밌어보여 풀어보았는데 그냥 단순히 DFS와 BFS 알고리즘을 통해 해결할 수 있는 문제였다. 아마 낮은 정답률의 원인이 정점 번호가 작은 것을 먼저 방문하는 것 때문인 거 같다. 방향이 주어지지 않았기 때문에 노드가 서로 바라보도록 연결하면 되겠다고 생각하여 연결되는 두 노드(node1, node2)를 입력받으면 그래프의 node1 위치에 node2를 추가하고 node2 위치에 node1을 추가하여 서로 연결시켰다. 여기서 중요한 점은 graph에 등록하고 등록된 그래프를 오름차순 정렬 시켜주는 코드이다. 정렬은 list의 기본 메서드인 sort()를 통하여 해결하였다. ..
백준 2583번 영역 구하기 문제 영역 구하기 문제는 빈 공간의 넓이와 갯수를 계산하여 출력하는 문제이다. 이번 문제는 BFS를 사용하면 간단히 해결할 수 있을 것 같아 BFS방식을 채택하여 해결하였다. "💡 문제 해결 아이디어 " 벽과 벽이 아닌 곳의 구분을 하기 위해 벽:1, 벽이 아닌 곳:0으로 구현하기로 정하고 문제 해결에 들어갔다. 우선 입력받은 가로, 세로의 길이를 통해 높이가 M, 너비가 N인 직사각형을 만든다. 반복문을 통한 2차원 배열 생성 방식으로 그래프를 생성하였고 각 1차원 배열의 값은 모두 0으로 채운다. 그럼 [[0,0,0,0,0,0], [0,0,0,0,0,0], ...] 과 같은 형태의 그래프가 그려진다. 그 다음 좌표 x1,y1,x2,y2값을 K번 입력받는데, 입력 받을 때마..
백준 1012번 문제 파이썬 "💡 문제 해결 아이디어" 유기농 배추 문제는 완전 탐색을 통해 해결해야하는 문제이다. 본인은 dfs를 통해 해결하였다. 0,0부터 n-1,m-1 까지 모두 돌며 값이 1인 곳(배추가 심어진 곳)을 찾는다. 지렁이는 상하좌우로 퍼져나갈 수 있기 때문에, 배추가 심어진 곳을 발견하면 그 구간에서 dfs를 돌려 인접해있는 1들을 모두 0으로 변경하고 1을 카운트한다. 이렇게 하면 인접해 있는 배추 그룹의 갯수를 전부 파악할 수 있어 지렁이가 총 몇 마리 필요한 지 구할 수 있다. "❗ 런타임 에러(RecursionError) 해결" dfs를 사용하면 편리하지만 벡준에서 지정한 기본 재귀 depth 때문에 런타임에러가 발생한다. 때문에 sys.setrecursionlimit()을 ..
백준 1181번 단어 정렬 문제입니다. https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 💡 문제 해결 아이디어 1181번 문제는 n개의 문자열을 입력받아 길이 순서대로 오름차순 정렬 후, 같은 길이의 문자열는 문자열 알파벳 순서대로 오름차순 정렬한 결과를 출력하는 문제입니다. 1. 이 문제는 같은 데이터를 받으면 안 되기 때문에 set으로 데이터를 입력받은 후 정렬을 위해 list로 변환시켜 word_list에 저장하고, 오름차순으로..
수 찾기 문제는 아래와 같은 방법으로 값을 배열에 받아 in 을 사용해 배열 안에 값이 있는지 확인해주면 해결 가능하다. 주의사항 a의 경우는 M안에 a에 해당하는 값이 있는 지 찾기 위한 용도로 사용될 것이기 때문에 a의 값을 사용할 일이 없어 set으로 받는다. 그렇지 않으면 시간 초과로 인해 문제를 해결할 수 없다. import sys input=sys.stdin.readline n = int(input()) a = set(map(int,input().split())) m = int(input()) M = list(map(int,input().split())) for i in range(len(M)): if M[i] in a: print(1) else: print(0)
