백준 1743 음식물 피하기

이 문제는 dfs / bfs 를 사용하는 문제이다.

똥이 주어진 곳을 0 으로, 일반 길을 'A'로 해서 0만 다닐 수 있는 길로 설정 후

0으로 지나다니는 길을 dfs로 지나온 길의 갯수를 세면 된다.

 

한번 연결되서 지나간 길은 방문 처리가 되므로, 중복으로 지나가지는 않는 점을 참고하면 된다.

import sys
sys.setrecursionlimit(10**9)
 
v, h, c = map(int, input().split());
graph = [['A' for _ in range(h)] for _ in range(v)];
step = [(1,0),(0,1),(-1,0),(0,-1)];
visited = [];
mx = 0;
for _ in range(c):
  y, x = map(int,input().split());
  if x == 0 or y == 0: continue;
  if x > h or y > v : continue;
  graph[y - 1][x - 1] = 0;
def canmove(s,y,x):
  if y+s[1] < 0:
    return False;
  elif y+s[1] > v - 1:
    return False
  elif x+s[0] < 0:
    return False
  elif x+s[0] > h - 1:
    return False;
  else:
    return True;
 
def dfs(y,x,v):
  if((y+1,x+1) not in visited and graph[y][x] != 'A'):
    visited.append((y+1,x+1));
    v[0] += 1;
    graph[y][x] = v
    for s in step:
        if canmove(s,y,x):
            dfs(y+s[1],x+s[0], v);
                
for i in range(v):
  for j in range(h):
    if((i,j) not in visited and graph[i][j] != 'A'):
      a = [0];
      dfs(i,j,a);
      mx = max(a[0],mx);
print(mx);
 
# 출력 확인용
for i in graph:
  print(i)

 

이 문제는 본인이 풀때 오답을 냈는데 아래 부분에서 잘못한 점이 있었다.

def dfs(y,x,v):
  if((y+1,x+1) not in visited and graph[y][x] != '*'):
    visited.append((y+1,x+1));
    global mx;
    mx = max(v,mx);
    graph[y][x] = v
    for s in step:
        if canmove(s,y,x):
            dfs(y+s[1],x+s[0], v+1);
                
for i in range(v):
  for j in range(h):
    if((i,j) not in visited and graph[i][j] != '*'):
      # 오답이었던 이유 이게 2에서부터 뻗어가는 거기 때문에 이전 단계의 값을 가져오면 최대 3이 되어버림...
      dfs(i,j,1);
print(mx);

 

백준에서 주어진 테스트케이스 외에 내가 찾은 테스트케이스는 아래와 같다. (정 보고싶으면 드래그하세요)

 

5 5 7
1 1
1 2
3 3
2 3
4 3
3 2
3 4