3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 문제 읽기 일단 처음 딱 문제를 읽었을 때는.. 복잡하게 여러 연산이 있는 것처럼 나왔지만 결국엔 직사각형의 연결 컴포넌트 개수를 구하는 문제라는 생각이 들었다. 다음 그림을 보면 쉽게 이해할 수 있을 것이다. 그래서 이를 이용해서 문제를 해결했다. 문제 풀기 처음에 풀이 과정을 다음과 같이 구상했다. 다시 정리해 보면 다음과 같다. 사각형 좌표를 입력 받아 사각형 정보를 배열에 저장한다. 모든 사각형을 맵에 그려준다. 사각형을 그린다는 것은 맵에 각 방향에 대해 이동 가능..

1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제 읽기 처음에 문제를 읽고 풀었을 때는 dfs로 풀었었다. 그런데 3퍼센트 쯤에 시간 초과가 나와서 그냥 다른 방법을 생각해야겠구나 싶었다. 최단 거리니까 다음과 같은 세 가지 방법이 있었다. 다익스트라 벨만포드 플로이드워샬 각각은 사용하는 경우가 다양한데, 처음엔 다익스트라? 생각했다가 시작 지점이 정해져 있지 않기 때문에 다익스트라를 하려면 여러 번 돌려야만 했다. 그래서 모든 지점에서 다른 모든 지점까지의 최단 거리를 ..

16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 문제 읽기 처음에 딱 읽었을 때는 DFS가 생각났다. 그래서 dfs로 짜다가.. 생각해보니 벽을 피해서 움직여야 하고, 8방으로 움직여야 한다. 맵의 크기가 매우 작긴 하지만, 벽을 피해서 이동하는게 최우선이기 때문에 중복 방문도 가능하다 생각했고, 경우의 수가 너무 많이 나올 것 같았다. 맵의 벽도 계속 이동 시켜서 넘겨줘야 하는데 너무 비효율적이라는 생각이 들었다. 게다가 DFS의 재귀 + 중복 방문 허용이 합쳐지면 처리를 해주지 않는 이상 무한 루..

2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 문제 읽기 처음에 문제를 읽었을 때에는 dfs를 써야겠다고 생각했다. 그렇게 풀었는데 백트래킹을 제대로 하지 않아서 인지.. 3%에서 계속 시간 초과가 났다 !! 너무 답답해서 그냥 풀이 방식을 바꿔보기로 했다. 글 읽기 - 어디가 틀렸을까요 ㅠ 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 위 글을 통해 힌트를 얻었다. 0-1 BFS를 이용하면 될 것 같았다. 잊고 있었던 알고리즘이다. 문제 풀기 0-1 BFS는 BFS처럼 방문..

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 읽기 문제는 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제이다. 근데 알고리즘을 어떤 걸 써야 하는지는 문제 이름에서 스포를 당하긴 했지만.. 플로이드 워샬 알고리즘이 잘 기억이 나지 않아서 처음엔 그냥 다익스트라를 N번 돌렸다. 그래도 플로이드 워샬 알고리즘도 정리할 겸 공부해서 다시 풀어보았다. 문제 풀기 다음과 같이 다익스트라와 플로이드 워샬로 풀었다. 다익스트라 모든 정점에서 다른 모든 정점까지의 최단 거리니까 다음 코드와 같이 모든 노..

그래프 문제에서 최단 경로를 구하는 알고리즘은 다음과 같다. Dijkstra 다익스트라 한 지점에서 다른 모든 지점까지 최단 거리 양의 가중치만 O(ElogV) Bellman-ford 밸만-포드 한 지점에서 다른 모든 지점까지 최단 거리 음의 가중치 허용 O(VE) Floyd-Warshall 플로이드 워샬 모든 지점에서 다른 모든 지점까지 최단 거리 음의 가중치 허용 O(V^3) 다익스트라와 밸만 포드에 대해서는 다음 포스팅에서 알아볼 수 있다. 다익스트라, Dijkstra Algorithm 코딩 문제에서 많이 볼 수 있는 그래프와 관련된 알고리즘을 공부해보자. 그래프에서 최단 거리를 구하는 알고리즘은 다음과 같은 것들이 있다. 💡 그래프의 최단 거리 구하는 알고리즘 1. 다익 rue-mi.tistory..