[백준] 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한 값이 모든 토마토가 익을 때까지 필요한 최소 일수이다. 토마토가 모두 익을 수 없을 때는 너비 우선 ..
[백준] 1012번 유기농 배추 파이썬 정답 코드
1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1. 문제 내용 2. 접근 방식 배추가 심어져 있는 땅을 입력받는다. maps 2차원 리스트를 모두 0으로 초기화한 다음에, 배추가 심어져 있는 장소를 1로 바꾸면 된다. 또한 배추가 심어져 있는 땅, 즉 1인 칸의 위치를 알고 있기 때문에 아직 방문하지 않은 배추가 심어진 땅을 대상으로만 bfs( ) 메서드를 실행하면 된다. 3. 정답 코드 from collections import deque def make_maps(ks): graph = [[0] * n for _ in..
[백준] 2667번 단지번호 붙이기 파이썬 정답 코드
2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 1. 문제 내용 2. 접근 방식 첫 시작점인 (0, 0)이 1일 수도, 0일 수도 있다. 이 문제는 기본적으로 2178번 미로탐색 문제와 해결 방식이 똑같다. 그러나 2가지 차이점 중 하나가 바로 시작점이 무조건 1이 아니라, 0과 1 모두 가능하다는 것이다. 따라서 이중 for문을 통해서 방문하지 않은 것 중에서 1인 칸을 찾은 후, bfs() 메서드를 실행해야겠다고 판단했다. 단지에 속하는 집의 수는 count 변수로 구한다. 미로 탐색 문제와의 또 다른 차이..
[백준] 2178번 미로 탐색 파이썬 정답 코드
2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1. 문제 내용 2. 접근 방식 너비 우선 탐색 사용 (1, 1)에서 상하좌우 인접한 칸을 확인하면서 너비 우선 탐색을 한다. 칸 수는 visited 2차원 리스트로 카운트한다. (1, 1)의 첫 번째로 방문하는 칸이고, 상하좌우에 붙어 있는 칸을 방문한다면 그것은 두 번째로 방문하는 칸이다. 즉, visited[0][0] = 1이면, 우측에 있는 칸을 방문한다면 visited[0][1] = visited[0][0] + 1 = 1 + 1 = 2로 계산된다. ** 편의상 (1, 1)칸은 (0, ..