문제 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 풀이 이러한 문제들의 graph는 2차원 ArrayList로 만들 수 있다. 연결되어 있는 컴퓨터 번호 쌍을 각각의 ArrayList에 추가해준다. 1번 컴퓨터와 연결되어있는 컴퓨터들을 찾는 문제로 1번 컴퓨터부터 시작하는 BFS와 DFS로 해결하는 문제이다. BFS로 해결하는 경우 Queue를 이용한다. 큐에서 꺼낸 ArrayList에 연결되어있는 번호가 방문한 적이 없다면, 그 번호로 시작하는 ArrayList를 queue에 추가해주고 cnt는 +1 해준다...

문제 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 재귀로 구현한 DFS와 큐로 구현한 BFS로 해결할 수 있다. 영역과 영역의 크기는 mutableList를 이용해 저장해주었다. graph는 false로 초기화 되어있는 BooleanArray를 이용했다. 입력받은 직사각형이 지나는 좌표는 true로 바꾸어준다. 이때 주어진 좌표의 기준점이 왼쪽 위(graph[0][0])가 아니라 아래(graph[rows][0])인 것을 주의해서 for문을 만들어 주어야한다. graph를 순회하며 ..

문제 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 재귀로 구현한 DFS와 큐로 구현한 BFS로 해결할 수 있다. 단지와 집의 수는 mutableList를 이용해 저장해주었다. 주어진 graph를 순회하며 방문한적이 없고 graph가 1인 경우 단지를 추가하고 DFS나 BFS를 호출한다. DFS의 경우에는 graph가 방문하지않고 1인 경우에 다시 DFS함수를 호출해주고, 호출될 때 마다 집의 수를 1 증가시킨다. BFS의 경우에는 해당하는 경우에 Queue에 추가해주고 집의 수를 1 증가시킨다. 리스트..

문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 입력받은 그래프를 너비 우선 탐색(BFS)을 이용해 풀이하면 된다. BFS로 풀이할 때, 일반적으로는 graph와 같은 크기로 Boolean 배열인 visited를 만들고 방문 체크를 해준다. 그렇지만 이번 문제에서는 visited를 사용하지 않았고, graph[x][y]가 1일 때만 graph[x][y]를 갱신해주는 방법을 이용하였다. graph[x][y]가 0인 경우(벽)와 1 이상인 경우(이미 방문함)에는 방문하지 않기 때문에 최단거리를 알 수 있다. 코드 import java..

문제 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 이 문제는 스택을 이용하여 해결할 수 있다. '('을 입력받은 경우 스택에 저장하고 ')'을 입력받은 경우에는 스택에서 제거하는 방법이다. 이 때, 스택이 비어있을 때')'을 입력받은 경우와 모든 입력을 처리 했는데 스택이 비어있지 않는 경우에는 입력받은 괄호 문자열이 잘못된 문자열인 것이다. 이번에는 mutableList를 이용해 스택을 구현해 보았다. 스택에서 push(n)에 해당하는 함수는 list.add(n)을 이..