Archive / BOJ / Python

1388번 바닥 장식

이왜틀?

이상하네 숫자가 크지도 않고 그냥 전체 탐색하면서 세어도 문제 없을 것 같은데

StringTokenizer st=new StringTokenizer(br.readLine()," ");
int r=Integer.parseInt(st.nextToken());
int c=Integer.parseInt(st.nextToken());
char[][] arr=new char[r][c];
int s=0;
for(int i=0;i<r;i++) {
    String l=br.readLine();
    s+=l.split("\\|").length;
    for(int j=0;j<c;j++) {
        arr[i][j]=l.charAt(j);
    }
}
for(int i=0;i<c;i++) {
    StringBuilder sb=new StringBuilder();
    for(int j=1;j<r;j++) {
        sb.append(arr[j][i]);
    }
    s+=sb.toString().split("-").length;
}
bw.write(s+"");

그냥 split 때리면 공백도 구간으로 쳐지지 않나?
할거였으면 정규식을 썼어야했다.
아니 진짜 직접 세기만 해도 통과했을 것 같은데

설계

문제 분류에 그래프가 들어있다.
그렇다면 DFS로 풀어주자.

구현

1. DFS

이어진 부분까지 - 면 가로,

면 세로로 탐색한다.

def dfs(x, y):
    visited[x][y] = True

    if board[x][y] == '-':
        ny = y + 1
        if ny < M and not visited[x][ny] and board[x][ny] == '-':
            dfs(x, ny)
    
    elif board[x][y] == '|':
        nx = x + 1
        if nx < N and not visited[nx][y] and board[nx][y] == '|':
            dfs(nx, y)

2. 수 세기

새로운 연결점인 경우 수를 세고 출력한다.

N, M = map(int, input().split())

board = []
for i in range(N):
    board.append(list(input().strip()))
        
visited = []
for i in range(N):
    row = []
    for j in range(M):
        row.append(False)
    visited.append(row)

count = 0
for i in range(N):
    for j in range(M):
        if not visited[i][j]:
            dfs(i, j)
            count += 1

print(count)

채점

반성

리스트 컴프리헨션을 쓰면 초기화가 한 줄로 가능하다.
익숙하지가 않아서 그냥 직접 초기화 때렸는데 앞으로는 익숙해지도록 하자.

코드 확인

Link to GitHub