[Python] 백준 11559, 프로그래머스 프렌즈4블록, 백준 13460

1. 문제: https://www.acmicpc.net/problem/11559

해당 문제는 그래프탐색 (영역) + 시뮬레이션 문제이다.

최단거리를 구하는게 아닌, 영역을 만들고 터뜨리는게 목적이므로 DFS와 BFS 모두 가능하다.

 

✅ DFS

board = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0

for i in range(12):
  board.append(list(input()))

def down():       # 터지면 중력에 의해 다른 뿌요가 나올떄까지 떨어짐
  for y in range(6):
    for i in range(10, -1, -1):
      for x in range(11, i, -1):     # 아래가 바닥이고, 위에가 뿌요일 경우
        if board[x][y] == "." and board[i][y] != ".":
          board[x][y] = board[i][y]
          board[i][y] = "."


def dfs(x, y, color):
  visited[x][y] = True
  temp.append((x, y))   # 터뜨릴 뿌요 좌표 리스트 추가

  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    if 0<=nx<12 and 0<=ny<6 and not visited[nx][ny] and board[nx][ny] == color:
       dfs(nx, ny, color)

while True:
  flag = True    # 반복문을 멈출 flag 변수
  visited = [[False] * 6 for _ in range(12)]

  for i in range(12):
    for j in range(6):
      if board[i][j] != "." and not visited[i][j]:   # 새롭게 영역을 탐색할 뿌요일 경우, 그래프탐색 실행
        temp = []
        dfs(i, j, board[i][j])

        if len(temp) >= 4:    # 같은색 뿌요들이 4개이상 모이게 되면 터짐
          flag = False
          for i, j in temp:
            board[i][j] = "."    # 뿌요 터뜨리기

  if flag:   # 더이상 터뜨릴 뿌요가 없다면
    break

  down()
  answer += 1   # answer를 한 반복문 루핑마다 도는 이유는, 여러개의 뿌요 그룹들이 터져도 연쇄 하나로 카운트하기 때문

print(answer)

 

✅ BFS

from collections import deque

board = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0

for i in range(12):
  board.append(list(input()))

def down():       # 터지면 중력에 의해 다른 뿌요가 나올떄까지 떨어짐
  for y in range(6):
    for i in range(10, -1, -1):
      for x in range(11, i, -1):     # 아래가 바닥이고, 위에가 뿌요일 경우
        if board[x][y] == "." and board[i][y] != ".":
          board[x][y] = board[i][y]
          board[i][y] = "."


def bfs(x, y, color):
  visited[x][y] = True
  q.append((x, y))
  temp.append((x, y))    # 터뜨릴 뿌요 좌표 리스트 추가

  while q:
    x, y = q.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0<=nx<12 and 0<=ny<6 and not visited[nx][ny] and board[nx][ny] == color:
        q.append((nx, ny))
        temp.append((nx, ny))
        visited[nx][ny] = True

while True:
  flag = True    # 반복문을 멈출 flag 변수
  visited = [[False] * 6 for _ in range(12)]

  for i in range(12):
    for j in range(6):
      if board[i][j] != "." and not visited[i][j]:   # 새롭게 영역을 탐색할 뿌요일 경우, 그래프탐색 실행
        q = deque([])
        temp = []
        bfs(i, j, board[i][j])

        if len(temp) >= 4:    # 같은색 뿌요들이 4개이상 모이게 되면 터짐
          flag = False
          for i, j in temp:
            board[i][j] = "."    # 뿌요 터뜨리기

  if flag:   # 더이상 터뜨릴 뿌요가 없다면
    break

  down()
  answer += 1   # answer를 한 반복문 루핑마다 도는 이유는, 여러개의 뿌요 그룹들이 터져도 연쇄 하나로 카운트하기 때문

print(answer)

 

2. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/17679

해당 문제 조건은 2 x 2 형태로 4개 붙어있는 경우 사라지는 유형으로, 위와 비슷하면서도 조건이 다르다.

 

def solution(m, n, board):
    answer = 0
    board = [list(i) for i in board]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    def down():
        for y in range(n):
            for i in range(m-2, -1, -1):   # 아래
                for x in range(m-1, i, -1):   # 위
                    if board[i][y] != "." and board[x][y] == ".":
                        board[x][y] = board[i][y]
                        board[i][y] = "."
    
    while True:
        pop_set = set()   # 사라질때 겹치는 좌표가 있을 수 있으므로 중복 제거를 위해 set 사용

        # 1. 2x2 같은 블록 찾기
        for i in range(m-1):
            for j in range(n-1):
                if board[i][j] == board[i+1][j] == board[i][j+1] == board[i+1][j+1] and board[i][j] != ".":
                    pop_set.update([(i, j), (i+1, j), (i, j+1), (i+1, j+1)])
                    # update: set에 한꺼번에 여러 원소를 추가하고싶을 때 사용함

        # 2. 제거할 블록이 없으면 멈춤
        if not pop_set:
            break
        answer += len(pop_set)

        # 3. 제거
        for x, y in pop_set:
            board[x][y] = "."
            
        down()
            
    return answer

 

3. 문제: https://www.acmicpc.net/problem/13460

"최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는가?" == "빨간 구슬이 구멍에 도달하기까지의 최단 거리 구하기"

즉, BFS를 활용하는 문제라고 할 수 있다.

문제를 풀이함에 있어서 핵심 조건은 다음과 같다.

- 왼쪽/오른쪽/위쪽/아래쪽으로 기울일 수 있으며 빨간공과 파란공은 동시에 움직인다. 단, 빨간공과 파란공은 겹칠 수 없다

- 파란 구슬이 구멍에 빠지면 실패이다.

- 더 이상 구슬이 움직이지 않을 때 동작을 그만둔다. (while True 에서 일정 조건에서 break하기)

- 만약 최단 거리가 10을 초과한다면 -1을 출력한다.

 

✅ 풀이

from collections import deque

n, m = map(int, input().split())
board = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(n):
  board.append(list(input()))
  for j in range(m):
    if board[i][j] == "R":
      red_x, red_y = i, j
    if board[i][j] == "B":
      blue_x, blue_y = i, j

def move(x, y, dx, dy):
    count = 0	    # 이동한 칸 수
    # 이동한 칸 수를 알게되면 어느 구슬이 더 많이 움직인지 알 수 있음

    while board[x+dx][y+dy] != '#' and board[x][y] != 'O':
        # 다음에 이동할 좌표가 벽이 아니거나 현재 좌표가 구멍이 아닐 때까지 이동함
        x += dx
        y += dy
        # 현재 좌표를 한칸 전진하고
        count += 1
        # 한칸 전진했으므로 +1을 해준다

    return x, y, count

visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]

visited[red_x][red_y][blue_x][blue_y] = True
q = deque([(red_x, red_y, blue_x, blue_y, 1)])
  
while q:
    red_x, red_y, blue_x, blue_y, n = q.popleft()

    # 구슬이 움직이는 횟수는 10번 이하여야 함
    if n > 10:
        break

    # 네 가지 기울이기 동작 시행
    for i in range(4):
        red_nx, red_ny, r_count = move(red_x, red_y, dx[i], dy[i])	# 빨간 구슬 이동
        blue_nx, blue_ny, b_count = move(blue_x, blue_y, dx[i], dy[i]) # 파란 구슬 이동

        # 빨간공과 파란공이 같은 위치에서 멈추면 (겹치게된다면)
        if red_nx == blue_nx and red_ny == blue_ny:
            # 움직임이 많은 구슬이 다른 구슬보다 한칸 적어지게 해서 안겹치게 처리함
            if r_count > b_count:
              red_ny -= dy[i]
              red_nx -= dx[i]
            else:
              blue_ny -= dy[i]
              blue_nx -= dx[i]
              
        # 파란구슬이 구멍에 도착했다면 실패
        if board[blue_nx][blue_ny] == 'O':
            continue

        # 빨간구슬이 구멍에 도착했다면 성공
        if board[red_nx][red_ny] == 'O':
            print(n)
            exit(0)

        # 구슬 이동을 마치고 도달한 좌표값이 예전에 방문했던 적이 없다면 새로 큐에 추가
        if not visited[red_nx][red_ny][blue_nx][blue_ny]:
            visited[red_nx][red_ny][blue_nx][blue_ny] = True
            q.append((red_nx, red_ny, blue_nx, blue_ny, n+1))

print(-1)

 

차례대로 뜯어보면,

 

1) 빨간 구슬이 "0"에 도달하는 최소 횟수를 구함 --> BFS

2) 그럼 BFS에 사용되는 방문 여부를 판단하는 visited 배열과 큐에는 어떤 내용이 들어가야할까?

 

BFS를 통해 탐색을 진행하면서 시시각각 바뀌는 변수를 들고다닌다 생각하면 편하다.

즉, 빨간 구슬의 좌표와 파란 구슬의 좌표, 그리고 각 좌표마다 구슬을 굴린 횟수가 다르므로 이를 들고다닌다.

 

따라서 visited는 visited[빨간 구슬 x][빨간 구슬y][파란 구슬 x][파란 구슬y]로 설계할 수 있도록 4차원 배열로 설계하고,

Q에는 (빨간 구슬 x, 빨간 구슬 y, 파란 구슬 x, 파란 구슬 y, 굴린 횟수) 튜플이 들어갈 수 있도록 설계한다.

 

visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]

visited[red_x][red_y][blue_x][blue_y] = True
q = deque([(red_x, red_y, blue_x, blue_y, 1)])
  
while q:
    red_x, red_y, blue_x, blue_y, n = q.popleft()

 

3) 그리고 빨간 구슬과 파란 구슬을 움직여야하는데, 조건이 있다.

- 각 기울이기 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을때까지, 즉 벽이거나 구멍을 마주치기 전까지 계속 굴리는것이다.

def move(x, y, dx, dy):
    count = 0	    # 이동한 칸 수
    # 이동한 칸 수를 알게되면 어느 구슬이 더 많이 움직인지 알 수 있음

    while board[x+dx][y+dy] != '#' and board[x][y] != 'O':
        # 다음에 이동할 좌표가 벽이 아니거나 현재 좌표가 구멍이 아닐 때까지 이동함
        x += dx
        y += dy
        # 현재 좌표를 한칸 전진하고
        count += 1
        # 한칸 전진했으므로 +1을 해준다

    return x, y, count

 

- 여기서 구슬을 굴리면서 count를 세는 이유는, 이후에 구슬을 겹치지 않도록 하기 위함이다. (빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다는 조건때문에, 파란 구슬이나 빨간 구슬 이동횟수를 따져서 둘 중 하나를 후퇴 시켜서 조정하기 위함)

 

    # 네 가지 기울이기 동작 시행
    for i in range(4):
        red_nx, red_ny, r_count = move(red_x, red_y, dx[i], dy[i])	# 빨간 구슬 이동
        blue_nx, blue_ny, b_count = move(blue_x, blue_y, dx[i], dy[i]) # 파란 구슬 이동

        # 빨간공과 파란공이 같은 위치에서 멈추면 (겹치게된다면)
        if red_nx == blue_nx and red_ny == blue_ny:
            # 움직임이 많은 구슬이 다른 구슬보다 한칸 적어지게 해서 안겹치게 처리함
            if r_count > b_count:
              red_ny -= dy[i]
              red_nx -= dx[i]
            else:
              blue_ny -= dy[i]
              blue_nx -= dx[i]

 

4) 이후 조건에 의해 BFS를 실행한다.

              
        # 파란구슬이 구멍에 도착했다면 실패
        if board[blue_nx][blue_ny] == 'O':
            continue

        # 빨간구슬이 구멍에 도착했다면 성공
        if board[red_nx][red_ny] == 'O':
            print(n)
            exit(0)

        # 구슬 이동을 마치고 도달한 좌표값이 예전에 방문했던 적이 없다면 새로 큐에 추가
        if not visited[red_nx][red_ny][blue_nx][blue_ny]:
            visited[red_nx][red_ny][blue_nx][blue_ny] = True
            q.append((red_nx, red_ny, blue_nx, blue_ny, n+1))

 

오늘의 배운점

1. Python Set 메소드

- add : 원소 추가

- remove: 원소 제거

- update : set에 한꺼번에 여러개의 원소를 추가하고 싶을 때

 

2. BFS에서 큐에 들어갈 튜플의 최소 길이 = visited 배열의 차원의 갯수 = 문제에서 시시각각 변하는 상태 변수의 갯수이다.

visited 배열과 큐를 설계할 때 매번 상태가 변하거나 조건을 따져야하는 변수가 몇개있는지 찾아보자

 

3. visited 배열은 "현재 상태를 탐색의 단위"로 삼기 위함이다. 즉 다음 탐색 범위를 지정하기 위함이므로 지나온 모든 경로를 방문처리할 필요는 없다.