[ProblemSolving] 백준 2667번, 프로그래머스 64061번 문제풀이

백준 2667번 DFS 문제와 프로그래머스 64061번 구현 문제에 대한 풀이를 작성하겠다. 각각의 문제 해설은 링크를 연결해두었으니 확인하면 된다.

 

백준 2667번 단지번호붙이기 (DFS) 문제 해설

2667번: 단지번호붙이기

단지의 수를 세어야 하기 때문에 깊이 우선 탐색을 사용하여 구현하면 된다.  깊이 우선 탐색의 과정은 다음과 같다.

 

1. 아파트가 있고, 아직 방문하지 않은 곳을 탐색한다.
2. 방문 처리를 하고, 아파트의 수를 세어준다.
3. 왼쪽, 오른쪽, 위, 아래의 방향으로 가상으로 이동한다.
4. 가상으로 이동한 곳이 방문하지 않고 방문 가능한 곳이라면 2번의 과정을 실행한다.
5. 더 이상 이동 가능한 곳이 없다면 1번의 과정으로 돌아간다.

위의 과정을 코드로 작성하면 다음과 같다.

 

# 백준 2667번 단지번호붙이기 (dfs)
def dfs(x, y):
  dx = [-1, 0, 1, 0] # 아래 왼쪽 위 오른쪽
  dy = [0, -1, 0, 1] # 아래 왼쪽 위 오른쪽
 
  visited[x][y] = True
 
  if data[x][y] == 1:
    answer[count] += 1
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx >= 0 and nx < n and ny >= 0 and ny < n:
        if not visited[nx][ny]:
          dfs(nx, ny)
 
n = int(input())
data = []
answer = []
visited = [[False] * n for _ in range(n)]
count = 0
 
for _ in range(n):
  data.append(list(map(int,str(input()))))
 
for i in range(n):
  for j in range(n):
    if data[i][j] == 1 and not visited[i][j]:
      answer.append(0)
      dfs(i, j)
      count += 1
 
print(len(answer))
answer.sort()
for i in answer:
  print(i)

 

• data는 단지의 정보를 입력받는 배열이다.
• answer는 각각의 단지가 가지고 있는 아파트의 수를 저장한 배열이다.
• visited는 방문 처리하는 배열이다.
• count는 아파트의 수를 저장하는 변수이다.

프로그래머스 64061번 크레인 인형 뽑기 게임 문제 해설

코딩테스트 연습 - 크레인 인형뽑기 게임

 

문제에서 moves는 인형 뽑기 기계의 가로 위치에 대한 정보를 담고 있다. 따라서 moves에 따른 세로 위치만 계산하여 바구니에 넣어주면 된다.

 

1번은 네오 2번은 무지, 3번은 콘, 4번은 어피치, 5번은 프로도이다. 해당 문제는 문제가 요구하는 조건을 다음의 과정에 맞게 구현하면 된다.

 

1. moves에 값(가로)에 맞는 가장 위에 있는 인형을 선택한다.
2. 선택한 인형과 바구니 가장 위에 있는 인형을 비교한다.
3. 두 인형이 같다면 count를 2 증가시켜주고, 두 인형을 바구니에서 뺴준다.
4. 두 인형이 다르다면 가장 위에 있는 인형과 선택한 인형을 바구니에 넣어준다.
5. 선택한 인형의 위치를 빈칸으로 만들어준다.
6. 1번의 과정을 반복한다.

위의 과정을 코드로 구현하면 다음과 같다.

 

# 프로그래머스 64061번 크레인 인형뽑기 게임 (구현)
def solution(board, moves):
    basket = [0]
    n = len(board)
    count = 0
 
    for i in range(len(moves)):
      for j in range(n):
        # 만약 빈칸이 아니라면
        if board[j][moves[i]-1] != 0:
          prevValue = basket.pop()
          # 배열의 맨 위에 값과 현재값 비교
          if prevValue == board[j][moves[i]-1]:
            count += 2
          else:
            basket.append(prevValue)
            basket.append(board[j][moves[i]-1])
          board[j][moves[i]-1] = 0
          break
    return count

 

해당 문제에서는 moves는 가로 위치의 정보를 가지고 있다는 것과 인형을 선택할 때마다 바구니에서 인형을 비교해주는 것을 생각하는 것이 중요했다.