[CodeUp] 2605번 : 캔디팡 (Python)

[CodeUp] 2605번 : 캔디팡 (Python)

 

 

목차

 

 

 

 

https://codeup.kr/problem.php?id=2605 

캔디팡

 

Python

 

방법 1-1 - 메모리 27724 / 시간 16 / 코드 길이 585B

 

본 문제는 DFS의 가장 기본이 되는 문제이다. 다만 색깔 정보에 따라 구별해야한다는 차별점만 있을 뿐이다.

DFS를 위해 stack list를 고민하고 풀면된다.

다만 여기서는 counting 정보를 포함하는 return을 통해 값을 처리하고자 했다.

 

이 방식은 색을 칠하는 flood fill 알고리즘 문제로 판단되기도 한다.

 

 

def dfs(x, y, t, v, p):  
  if x<0 or x>=len(t) or y<0 or y>=len(t[0]):
    return 0
  
  c = 0 
  if not v[x][y] and t[x][y] == p:
    v[x][y] = t[x][y]
    c += 1
    c += dfs(x-1, y, t, v, p)
    c += dfs(x+1, y, t, v, p)
    c += dfs(x, y-1, t, v, p)
    c += dfs(x, y+1, t, v, p)
  return c

t = [list(map(int, input().split())) for _ in range(7)]
visited = [[0 for _ in range(len(t[0]))] for _ in range(len(t))]

s = 0
for i in range(len(t)):
  for j in range(len(t[0])):
    if dfs(i, j, t, visited, t[i][j]) >= 3:
      s += 1      
print(s)

 

방법 1-2 - 메모리 27724 / 시간 16 / 코드 길이 424B

 

방법 1-1을 조금 정리한 것

 

t = [list(map(int, input().split())) for _ in range(7)]
v = [[0 for _ in range(7)] for _ in range(7)]

def dfs(x, y, p):  
  if x<0 or x>6 or y<0 or y>6:
    return 0
  if not v[x][y] and t[x][y] == p:
    v[x][y] = t[x][y]
    return 1+dfs(x-1,y,p)+dfs(x+1,y,p)+dfs(x,y-1,p)+dfs(x,y+1,p)
  return 0

s = 0
for i in range(7):
  for j in range(7):
    if dfs(i, j, t[i][j]) >= 3:
      s += 1      
print(s)

 

 

방법 2-1 - 메모리 27724 / 시간 16 / 코드 길이 502B

 

전역 list를 통한 for문 돌리기

 

t = []
for i in range(7):
  t.append(list(map(int, input().split())))  
v = [[0 for _ in range(7)] for _ in range(7)]

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

def dfs(x, y):
  c = 1
  v[x][y] = t[x][y]

  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if nx<0 or nx>6 or ny<0 or ny>6:
      continue
    elif not v[nx][ny] and t[x][y] == t[nx][ny]:
      c += dfs(nx, ny)
  return c

s=0
for i in range(7):
  for j in range(7):
    if dfs(i,j) >= 3:
      s+=1
print(s)