6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제 풀기 이 문제에서 보통의 맵 문제와 다른 점은 거울이다. 하지만 거울의 개수는 그냥 이동 방향의 변화 횟수를 카운트하면 되기 때문에 그것만 떠올리면 그리 어렵진 않다. 처음에 딱 읽었을 때는 BFS가 생각났다. BFS로 이동하면서 이동 방향이 이전과 바뀌면 카운트를 하면 되지 않을까? 생각했다. 그리고 재방문이 안 된다는 걸 고려해서 순회하는 방향을 계속 바꿔주는 식으로 문제를 풀었다. 그렇게 BFS로 풀고 제출했더니 3퍼센트에서 틀렸다. 그래서 ..

9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 문제 읽기 이 문제는 풀기 위해서 다익스트라부터 0-1 BFS 알고리즘까지 다시 공부하고 오게 한 문제이다. 전혀 감이 잡히지 않았고.. 처음에는 단순히 한 명 먼저 탈출하고 그 다음에 다른 애가 탈출하면 되지 않을까 했지만, 테케 1, 2, 3을 봤을 때 3번은 그런 식으로는 통과가 불가능했다. 둘이 같이 나가야 했다. 그래서 엄청 시간을 많이 쏟은 문제였다. 결국 질문 게시판을 봤고,, !! 힌트를 얻어서 다음과 같이 풀었다. 문제 풀기 일단 결론부터 말하면 세 번의 0..

14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 문제 읽기 처음에 딱 읽었을 때는 문제가 제대로 이해가 되진 않아서 예시 보면서 이해했었는데, 단순하게 점프를 한 번 하면 0은 다 통과하고 1 테두리를 만날 때까지 BFS로 퍼져나가면 된다. 그리고 그 다음엔 1 테두리를 없애고 또다시 0은 다 통과하고 1 테두리를 만날 때까지 BFS로 퍼져나간다. 이를 반복한 횟수를 리턴하면 된다. 주어진 시작 점에서부터 BFS로 퍼져나가면 되기 때문에 문제만 이해했다면 알고리즘은 그리 어렵진 않은 문제이다. BFS..

2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 읽기 일단 맵이 0 또는 1로 이루어져 있고, 흰 방만 지나갈 수 있으며, 검은 방을 바꾸는 것을 최소로 해야 한다. 이런 문제는 0-1 BFS로 바로 해결할 수 있다. 0-1 BFS에 대한 설명은 다음에서 볼 수 있다. 0-1 BFS 0-1 BFS란? 💡 0-1 BFS 가중치가 0 또는 1로만 주어진 그래프에서, 시작 노드가 주어졌을 때 다른 모든 노드로의 최단 경로를 찾고자 할 때 사용하는, BFS를 응용한 알고리즘이다. 보편적으로 그래프 rue-mi...

1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 읽기 이 문제는.. 처음에 읽었을 때 다익스트라를 공부한 후에 풀려고 했던 BOJ 9376 탈옥 문제의 쉬운 버전처럼 느껴졌다. 사실 MAP 형태로 주어지는 문제에서 다익스트라로 풀어본 적이 없어서, ‘이걸 어떻게 다익스트라로 봐야 하지?’란 생각으로 도저히 방법을.. 모르겠더라. 삽질. 내가 그래프를 만들자(?) 그래서 처음에는 좀 멍청한(?) 짓을 했다. 0으로 묶인 부분끼리 한 집합으로 보고, 이걸 노드로 보고 그 사이의 1 최소..

0-1 BFS란? 💡 0-1 BFS 가중치가 0 또는 1로만 주어진 그래프에서, 시작 노드가 주어졌을 때 다른 모든 노드로의 최단 경로를 찾고자 할 때 사용하는, BFS를 응용한 알고리즘이다. 보편적으로 그래프에서 최단 경로를 찾을 때 사용하는 다익스트라 알고리즘의 경우, 시간 복잡도가 O(ElogV)인 반면, 0-1 BFS의 시간 복잡도는 O(V + E)로 선형 시간에 해결할 수 있는 효율적인 알고리즘이다. 다익스트라에 대해 알고 싶다면 다음 링크를 참조하면 좋을 것 같다. 다익스트라, Dijkstra Algorithm 코딩 문제에서 많이 볼 수 있는 그래프와 관련된 알고리즘을 공부해보자. 그래프에서 최단 거리를 구하는 알고리즘은 다음과 같은 것들이 있다. 💡 그래프의 최단 거리 구하는 알고리즘 1. ..