[백준] 4693번 섬의 개수 파이썬 정답 코드
4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 1. 문제 내용 2. 접근 방식 대각선까지 고려해야 한다. 상하좌우를 고려하는 기존 너비 우선 탐색 방식에서 대각선만 추가로 고려하면 된다. 따라서 파란색 별의 위치를 (0, 0)이라면, 상하좌우를 포함한 대각선까지 포함하는 모든 좌표들을 directions 리스트에 담아서 탐색하자. 3. 정답 코드 from collections import deque while True: def count_island(a, b): queue = deque([[a, b]]..
[백준] 10026번 적록색약 파이썬 정답 코드
10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. 문제 내용 2. 접근 방식 적록색약일 때와 아닐 때를 if문으로 구분하여 코드 중복을 줄이자. 적록색약이든 아니든, 구역을 세는 것은 똑같은 BFS 알고리즘을 사용하기 때문이다. 적록색약이 아닐 때는 R, G, B가 모두 다르므로, graph[x][y] == graph[dx][dy]일 때만 [dx][dy]를 방문한다. 반면 적록색약일 때는 R, G일 때와 B일 때를 구분하여 graph[dx][dy] 방문 여부를 결정한다. graph[x][y]가 'B'..
[백준] 11724번 연결 요소의 개수 파이썬 정답 코드
11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 1. 문제 내용 2. 접근 방식 너비 우선 탐색 방식으로 연결 요소 파악하기 처음에는 DFS (깊이 우선 탐색)으로 코드를 작성하여 제출하였지만, RecursionError가 나서 BFS로 바꾸었다. 집합을 사용하여 BFS에서 시간 줄이기 visited 리스트로 방문 여부를 체크하는 일반적인 코드는 아래 코드처럼 마지막에 모든 노드를 순회하면서 bfs 메서드를 호출하여야 했다. result = 0 fo..
[백준] 7576번 토마토 파이썬 정답 코드
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 문제 내용 2. 접근 방식 토마토가 익는 날짜를 파악하기 위해 graph[x][y] 값을 누적하자 초기 익은 토마토(i, j)는 1이다. 다음 날인 첫째날, 해당 토마토의 상하좌우에 있는 토마토는 (i, j) + 1 = 1 + 1 = 2가 된다. 이런 식으로 이전 날짜에 하루를 더하는 방식으로 0을 채워나가다 보면, 최대 날짜 값에서 -1한 값이 모든 토마토가 익을 때까지 필요한 최소 일수이다. 토마토가 모두 익을 수 없을 때는 너비 우선 ..