[백준] 1697번 숨바꼭질 파이썬 정답 풀이
https://www.acmicpc.net/problem/16971. 풀이BFS 알고리즘을 사용하자문제에서 말하는 최소 시간은 결국 수빈이가 동생까지 가는 데 이동하는 최단 거리로 치환할 수 있다. 또한 앞으로 1칸 이동, 뒤로 1칸 이동, 순간 이동은 모두 이동하는 데 1초가 걸린다. 즉, 모든 이동 방식의 가중치가 모두 1이다. 따라서 이 문제는 가중치가 1로 동일한 그래프에서 최단 경로를 찾는 것이므로 BFS 알고리즘이 적합하다. 참고로 BFS는 노드를 한 번만 방문하면 되며, 처음으로 노드를 방문한 시점이 가장 빠른 시간임을 보장한다. 번외로 dp를 통해 문제를 해결할 수는 있지만, dp는 일반적으로 이동에 따른 가중치가 서로 다른 경우에 활용한다. 2. 정답 코드from collections..
[프로그래머스] 리코쳇 로봇 파이썬 정답 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 풀이최소 거리를 찾는 bfs의 변형우선 노드과 노드 간의 최소 거리를 찾는 알고리즘인 bfs를 사용해야 한다.그러나 일반 bfs는 현재 좌표 (x, y)에서 상하좌우 한 칸씩만 이동하지만, 이 문제에선 장애물이나 게임판 가장자리를 만날 때까지 쭉 이어서 값을 더해줘야 한다. 예를 들어 (x, y)에서 아래로 이동할 때는 (x - 1, y)에서 멈추는지 확인하고 아니라면 (x - 2, y)에서 다시 확인하고 (x - 3, y), (x - ..
[프로그래머스] 가장 먼 노드 파이썬 풀이
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..