838. Push Dominoes
https://leetcode.com/problems/push-dominoes/
문제
풀이(처음 풀었던 답)
경우의 수를 알아보자.
dominoes[i] == "."이면 넘어간다.
1. s = -1(시작 초기값)이고 i = "L"일 때 ex) ...L => LLLL
2. s = -1(시작 초기값)이고 i = "R"일 때 ex) ...R => ...R 하지만 s = 3(R인덱스)으로 변경한다
3. s != -1이고 i = "R"일 때 ex) R...R => RRRRR 하지만 s = 4(R인덱스)로 변경한다.
4. s != -1이고 i = "L"일 때 ex) R...L => RR.LL 하지만 s = -1로 변경한다.
여기서 s != -1 이고 i = "L"일 때가 중요한데
R...L에 개수는 5이다. tmp = 2가 되고 R,L를 각각 2개씩, .을 5-22 =1개씩 추가한다.
R..L에 개수는 4이다. tmp = 2가 되고 R,L를 각각 2개씩, .dmf 4-22=0개씩 추가한다.
또한 마지막일 때를 확인해야하는데 s == -1(초기값이라면) "."을, 아니라면 "R"을 추가해준다.
결과
풀이(BFS)
처음 풀었던 풀이는 특정한 알고리즘을 사용하지 않아서 다른 방법을 찾아보았다.
이 문제를 BFS로 풀 수 있는데 dominoes = "R...L"을 가지고 설명해보자면
1. deque에 "."을 제외한 (인덱스, 문자) 저장한다.
=> deque = {(0, "R"),(4, "L")}
2. deque가 비워질 때까지 while문을 돈다.
3. i,d = deque.popleft()하여 조건을 확인한다.
4. dominoes[i+1] == "."이고 dominoes[i+2] != "L" 인지 확인한다.
=> dominoes = "RR..L" deque = {(4,"L"), (1, "R")}
5. i,d = deque.popleft() => i, d = 4, "L"
6. dominoes[i-1] == "." 인지 확인한다.
=> dominoes = "RR.LL" deque = {(1, "R") (2, "L")}
7. i, d = deque.popleft() = >i, d = 1, "R"
8. dominoes[i+1] == "." and dominoes[i+2] == "L"이므로 넘어가고 popleft()해준다.
=> dominoes = "RR.LL" deque = {}
결과(BFS)
