문제의 조건 자체는 엄청 쉬워보였다.

일반적인 bfs문제에 그저 블록 파괴 기능만 추가하면 의외로 쉽게 풀릴 줄 알았다... 그 때는...

접근 1)  더이상 순회 불가능 시 벽 파괴해보기

우선 그래프를 순회하며 만난 벽들을 모두 리스트에 담아 기록해둔다.

이후 큐의 모든 원소를 소모하였을 때, 도착점에 도달하지 못했다면, 리스트에서 벽을 하나씩 꺼내어 해당 벽을 부수고, 다시 순회를 해 주었다.

문제 1)  너무 비효율적인 순회

접근법 자체는 빠르게 떠올렸지만, 그리 좋은 접근법은 아니었다. 입력대로 초기화 될때의 상태를 간직하는 원본 그래프를 준비하고, 순회 시 마다 복사본 그래프를 만들어 순회를 해주었는데, 이건 메모리 측면에서나, 실행시간 측면에서나 너무 비효율적이었다.

문제 2)  한번에 순회를 완료했을때 문제.

이게 가장 큰 문제였다. 예제들은 모두 한번에 순회가 불가능했기  때문에 벽을 한번 부수고 순회하는 것이 최단거리였다.

하지만  https://www.acmicpc.net/board/view/147795  이 예제대로 막힌 벽 없이 한번에 순회가 완료되면 바로 메소드가 종료되어 올바른 답을 얻을 수 없었다.

때문에 다른 접근법을 찾아보기로 했다.

보완 1)  사용하는 그래프를 2개로 제한해보기

기존에 순회할 때 마다 무한정 늘어나는 그래프의 수를 제한하고자, 벽을 부수지 않는 경우, 벽을 부수는 경우 둘로 나누어 두 그래프만 사용해보기로 했다.

두 그래프를 유기적으로 묶어, 일반 그래프가 벽을 만나면, 벽을 부수는 그래프의 값을 증가시키고, 다시 벽을 부수는 그래프가 일반 그래프에 영향을 주어 순회를 하는 방식으로 해보았다.

또한 계속해서 벽을 뚫는것을 방지하기 위해, 벽이 벽을 만나면 순회하지않고, 건너뛰기로 했다.

문제 3)  벽을 한번 이상 부셔버림

알고리즘 특성상 연속된 벽은 통과 못하지만, 띄엄띄엄 존재하는 벽이라면 무한정으로 뚫고 지나가버리는 치명적인 문제점이 있었다. 따라서 벽을 몇번 뚫었는지 저장해두어야 한다는걸 깨닳았다.

문제 4) 벽을 부순건지 아닌지의 모호함

첫번째 칸이 0으로 되어있기 때문에, 첫번째 칸이 벽을 만나 벽을 부수게 되었을 때, 값이 1로 되어 벽을 부순 것인지, 벽을 부수지 않은 것인지 판별을 할 수 없는 문제가 있었다.

보완 2)  그래프를 하나로, 방문처리를 set이 아닌 배열로

그래프의 값을 변조하는 방식이 그다지 효과적이지 않다는 것을 깨달았다. 대신에, 기존에 방문처리를 해주던 HashSet 대신 bool 배열을 이용하여 해당 칸을 방문처리를 대신해 주었다. 이럼으로써 4번 문제가 깔끔히 해결되었다.

보완 3) 모든 정보를 저장해두자

지난번에 풀었던 사다리 게임 문제에서 클래스를 만들어 좌표값 , 이동한 거리, 이동할 좌표값을 저장해두었던 것에서 아이디어를 얻었다. 이번엔 튜플을 이용하여 좌표값, 벽을 부신 횟수, 이동한 거리를 저장하기로 하였다.

이 정보들을 바탕으로, 이동가능 여부, 벽 파괴 가능 여부를 판단할 수 있게 되었다.

코드)

dfs던 bfs던 아무 그래프 순회 알고리즘을 사용하여 1번 정점으로부터 방문 가능한 모든 정점의 개수를 요구하는 문제이다.

주의해야 할 점은 '1번 컴퓨터' 로 부터 감염될 수 있는 컴퓨터의 수를 구하는 문제이기 때문에, 1번 정점은 빼주고 개수를 구해주어야 한다.

이런식으로 서로 간선으로 연결되어있는 정점들의 집합을 하나의 연결 요소라고 한다.

이 주어진 그래프를 토대로 몇개의 연결 요소가 나오는지 구하는 문제이다.

문제에서 주어지는 정점의 개수는 1000개이다. 이를 일반적인 인접행렬로 표현하려면 1000 * 1000의 배열이 필요하므로, 메모리도 아끼고 실행 시간도 줄일 겸 각 정점이 어느 정점과 연결되어있는지 표현하는 인접행렬로 구현하였다.

문제를 풀기 위해서 dfs를 사용하여 순회하지 않았던 연결 요소라면 true를 반환하여 결과값에 1을 더하고, 순회하였던 연결 요소라면 false를 반환하도록 해주었다.

이번에는 너무 귀찮아서 스택을 직접 구현하지 않았다.

스택 관련해서 푼 문제중 의외로 제일 쉬웠다.

아파트 문제를 탑 문제처럼 풀었더니 아주 쉽게 풀 수 있었다.

다만 입력이 너무 많았던 것을 고려하지 못하여 시간초과가 났는데,

StreamReader와 StringBuilder를 사용하니 바로 해결되었다.

며칠전 올린 탑 문제와 비슷한 문제이다.

탑 문제는 가장 가까운 신호를 수신하는 탑의 번호를 출력하는 거라면

이번 문제는 한 탑보다 큰 탑이 올때 까지의 모든 탑(아파트) 의 개수를 구해서 더하여 출력하는 문제이다.

입력받은 배열의 0번지부터 n - 1번지까지 돌아가며 스택의 맨 위값과 비교하여 같거나 작다면 자신보다 작은 값이 나올때까지 계속 pop해주었다.

pop을 모두 수행 한 이후 (stack이 모두 비게됨 / stack의 맨 위값이 현재 배열의 값보다 큼)

남은 스택의 원소 만큼 결과값에 넣어 주었다. (여기서는 stack.size로 따로 변수를 만들어 주었으나, stack.top + 1을 사용하면 좋을 듯 하다.)

(이 과정은 현재 아파트의 옥상을 볼 수 있는 아파트의 수를 구하는 과정이다.)

마지막으로 현재 아파트의 높이를 가리키는 주소를 스택에 넣어주고 다음 회차로 진행해 주었다.

또한 주어지는 결과값이 매우 크기때문에 (단적인 예로 799,999 + 799,998 + 799,997 .... + 1) 결과를 저장할 변수를 int형으로 하면 오버플로우로 인한 오류가 난다.

그렇기 때문에 long형을 사용해야 한다.

입력받은 문자열을 하나씩 되짚어가며

여는 괄호 " ( " 를 만나면 일단 스택에 저장한다.

이후 닫는 괄호 " ) " 를 만나게 되면       (0번 인덱스에 오는 닫는 괄호는 의미 없으니 거르는 코드를 추가해 주었다)

바로 직전 괄호가 여는 괄호인 경우 : 스택에서 해당 괄호를 제거 해 주고 스택에 남은 여는 괄호만큼 결과값에 추가

직전 괄호가 여는 괄호가 아닐 경우 : 스택에서 가장 앞에 있는 여는 괄호를 제거해주고, 결과값에 1 추가

이런식으로 진행해 주었더니 한번에 정답을 얻을 수 있었다

출력값들을 StringBuilder형 변수에 넣고 출력하는 과정에서 마지막에 생기는 공백을 없애기 위한 코드인

if (sb[sb.Length - 1] == '\n')

이 코드가 sb의 길이가 0인 경우 (n번의 입력동안 push만 한 경우) indexOufOfRange 에러가 나는 실수를 했다.

은근히 어려웠다...

덱을 구현하기 위해 원형 큐를 응용한 것까지는 좋았지만, 큐처럼 front는 항상 빈공간(null)을 가리키려고 해서 더욱 헷갈렸던 것 같다.