BFS

문제 요구사항 "O" 를 "X"로 flip 하라. 단, 가장 자리에 맞닿은 "O"의 경우 뒤집으면 안되며, 이 가장자리와 인접한 다른 "O"의 경우에도 뒤집지 않는다. 풀이 방법 (알고리즘 : BFS) 우선 M*N 배열에서 "O" 가 있는 칸의 위치 (i, j) 를 구한다. -> island 집합에 저장 가장자리에 있는 "O" 를 찾아서, "O"와 인접한 칸들까지 BFS로 찾아서 island 라는 집합에서 빼준다. 남아있는 좌표들은 X 로 flip 이 가능한 위치이므로 모두 변환해 준다. from collections import deque class Solution: def solve(self, board: List[List[str]]) -> None: N = len(board[0]) M = len(b..

https://www.acmicpc.net/problem/14714 14714번: 홍삼 게임 (Easy) 첫 번째 줄에 “질서 있는 홍삼 게임”의 참가자의 수 N(2 ≤ N ≤ 500), 은하가 먼저 지목한 사람의 번호 A와 두 번째로 지목한 사람의 번호 B(1 ≤ A, B ≤ N, A ≠ B), 각 지목권의 지목 간격을 나타내 www.acmicpc.net 문제 유형을 보면 힌트를 얻을 수 있는데, BFS를 사용하여 풀 수 있는 문제였다.. 방문 처리를 할 때 지목권 a를 가질 사람을 탐색 & 지목권 b를 가질 사람을 탐색 해야 하며 각 turn 마다 지목은 한번만 하므로 이를 3차원 배열로 나타낼 수 있다는 것이 이 문제의 핵심이었다 즉 이를 3차원 배열로 표현하게 되면 visited[지목권 종류][a..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net BFS 로 풀었다 상하 이동 처리만 신경써주면 된다 하지만 나는 삽질을 몋시간동안 했는지 모르겠다 근데 그 이유가 queue에서 뺄 때 popleft 가 아니라 pop() 을 써서 그렇다 .. 어이없다 ; from collections import deque # 방향 이동 - 동서남북 + 상하 dx = [-1, 1, 0, 0, 0, 0] dy = [0, 0, -1, 1, 0, 0] dz = [0, 0,..

https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 1. 치킨집을 두개 지정해주어야 한다. 이를 combination을 이용하여 간단히 구현했다. 2. 치킨집 2개를 뽑는 모든 조합을 brute force로 확인한다. 그리고 왕복거리가 최소가 되는 경우를 구한다. 3. bfs는 치킨집 2개를 start node라고 가정하고, 치킨집에서 각각의 노드들을 방문하며 왕복거리를 계산했다. 4. answer 를 sort해서 가..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net X위치가 결국 세가지 방법인 X-1, X+1, 2*X 로 이동할 수 있는데, bfs를 이용해서 최소시간을 찾도록 풀었다. 단, 최소시간을 찾아야 하므로 이미 방문한 위치는 다시 방문하지 않도록 visited 리스트를 통해서 방문 여부를 체크했다 걸린 시간은 노드의 위치와 함께 queue에 넣어서 queue에 append (순간 이동을 한 경우) 할때마다 time + 1을..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net DFS로 풀이했다. 나 근데 가로 세로가 아직 헷갈린다;; 아이디어는 다음과 같다. n = 7, m = 5 사이즈의 2차원 배열 (= 그래프) 가 있다고 생각하면, 각 칸을 모두 0으로 초기화 시킨다 입력되는 직사각형 부분에 해당하는 칸들은 2차원 배열에서 1로 표시한다. 1은 이미 방문된 노드라는 의미이다. 그후 전체 2차원 배열을 이중 for문으로 하나씩 칸의 값을 체크하면..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1) 적록색약이 아닌 사람 : array를 바꿀 필요 없이 BFS로 총 구역이 몇개인지 구한다. -> 어떻게 count를 하는가 ???가 또 관건인데... bfs에서 같은 문자가 계속 나오면 배열 c를 1로 표시를 해둔다. 그러면 이경우 R와 같은 위치에는 1이 나머지 배열은 아직 0이겠지요 ?? 이후 이중 for 문에서 if c[i][j] == 0: bfs 배열 c[i][j] 값이 0이면..

와 대박이다 이거 풀이의 핵심 알고리즘이 뭔지 아세여????놀랍게도 bfs임 와이파이 모양으로 확장하는거 왠지모르게 bfs는 와이파이 모양이 떠오른다.. 그리고 그렇게 생각하면 쉽게 이해된다) 자자 암튼 코드는 이렇다 # 1697 from collections import deque N, K = map(int,input().split()) MAX = 10 ** 5 dist = [0] * (MAX+1) def bfs(): q = deque() q.append(N) while q: x = q.popleft() if x == K: print(dist[x]) break for nx in (x-1, x+1, x*2): if 0