[프로그래머스] 가장 먼 노드 파이썬 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 1번 노드에서부터 각 노드까지의 최단 거리를 구해야 하므로, BFS를 활용하자 그래프를 탐색하는 방법은 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있다. 이중 최단 거리를 구하는 데는 BFS를 사용한다. 사실 각 노드를 연결하는 간선의 비용을 모두 1로 둔 채 최소 비용을 구하는 다익스트라 알고리즘을 사용할 수도 있지만, 굳이 2차원 배열인 다익스트라를 사용하지 않아도 된다...
[백준] 16234번 인구 이동 파이썬 풀이
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 1. 풀이 모든 국가를 방문하면서 너비 우선 탐색(bfs)로 연합을 확인하자 N x N 크기의 땅에는 1개 이상의 연합이 존재할 수 있다. 즉, 위 그림처럼 그래프가 여러 개 존재할 수 있다는 것이다. 따라서 땅을 한 칸, 한 칸 방문해서 해당 국가가 이루는 연합 정보를 알아내야 한다. 이때 어떠한 연합에 포함된 국가는, 이전 bfs 과정에서 방문했었다는 의미이다. 따라서 재방문을 ..
[백준] 14502번 연구소 파이썬 정답 풀이
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 접근 방식 최악의 경우는 62C3 이므로, 충분히 조합으로 문제를 풀 수 있다. 전체 빈 칸들 중에서 3개를 선택한 모든 경우의 수를 계산해도 되는지 먼저 파악했다. 지도의 가로, 세로 크기는 최대 8이므로, 최대 64개의 칸이 존재할 수 있고, 그 중 바이러스가 최소 2칸을 차지하므로 빈 칸의 개수는 최대 62개이다. 62개 중에서 3개를 순서 상관 없이 고르는 것이므로 위 조합이 나왔고, 대략 2^1..
[백준] 14940번 쉬운 최단거리 파이썬 풀이
https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 1. 접근 방식 (x, y) 지점의 상하좌우 지점으로부터 최단 거리를 알아낼 수 있다. 오직 가로와 세로로만 움직일 수 있으므로, 어떤 지점에서 이동할 수 있는 경로는 상하좌우밖에 없다. 예를 들어 2의 위치가 (1, 1)일 때, 이 지점의 상하좌우 즉 (0, 1), (2, 1), (1, 0), (1, 2) 지점으로부터 2까지 가는 최단 거리는 1이다...
[백준] 7569번 토마토 파이썬 풀이
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 1. 접근 방식 3차원 리스트를 사용하자. 기존 2차원 리스트에서 상하좌우를 이동할 때 direction = [ [1, 0], [0, 1], [0, -1], [0, 1] ]이라는 방향 리스트를 사용했던 것을 떠올려보자. 이 문제에서는 단순히 높이라는 하나의 차원이 더해졌을 뿐이므로, 기본 접근 방식은 동일하다. 토마토를 n x m 크기의 상자에 담는데, 이 상자가 h개일 뿐..
[백준] 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한 값이 모든 토마토가 익을 때까지 필요한 최소 일수이다. 토마토가 모두 익을 수 없을 때는 너비 우선 ..
[백준] 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..