<div id="readability-page-1" class="page"><div><h2 id="문제">문제</h2>
<a href="https://www.acmicpc.net/problem/11123">양 한마리... 양 두마리...</a>
<h2 id="풀이">풀이</h2>
<ul>
<li>dfs 순회하며 '#'을 카운팅</li>
</ul>
<h2 id="코드">코드</h2>
<pre><code>public class Main {
 static int h, w;
 static char[][] board;
 static boolean[][] visited;
 static int[] dx = {0, 1, 0, -1};
 static int[] dy = {-1, 0, 1, 0};
 
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 
 int t = sc.nextInt();
 
 sc.nextLine();
 
 for(int T = 0; T &lt; t; T++){
 h = sc.nextInt();
 w = sc.nextInt();
 sc.nextLine(); 
 
 board = new char[h][w];
 visited = new boolean[h][w];
 
 for(int j = 0; j &lt; h; j++){
 board[j] = sc.nextLine().toCharArray();
 }
 
 int answer = 0;
 
 for(int i = 0; i &lt; h; i++){
 for(int j = 0; j &lt; w; j++){
 if(board[i][j] == '#' &amp;&amp; !visited[i][j]){
 dfs(i, j);
 answer++;
 }
 }
 }
 System.out.println(answer);
 
 }
 sc.close();
 }
 
 private static void dfs(int x, int y){
 visited[x][y] = true;
 
 for(int i = 0; i &lt; 4; i++){
 int nx = x + dx[i];
 int ny = y + dy[i];
 
 if(nx &gt;= 0 &amp;&amp; nx &lt; h &amp;&amp; ny &gt;= 0 &amp;&amp; ny &lt; w &amp;&amp; board[nx][ny] == '#' &amp;&amp; !visited[nx][ny]){
 dfs(nx, ny);
 } 
 }
 }
 }
</code></pre>
<h2 id="정리">정리</h2></div></div>

삶도 재입학이 되나요?

문제
양 한마리... 양 두마리...
풀이
dfs 순회하며 '#'을 카운팅
코드
public class Main {
 static int h, w;
 static char[][] board;
 static boolean[][] visited;
 static int[] dx = {0, 1, 0, -1};
 static int[] dy = {-1, 0, 1, 0};
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 int t = sc.nextInt();
 sc.nextLine();
 for(int T = 0; T < t; T++){
 h = sc.nextInt();
 w = sc.nextInt();
 sc.nextLine(); 
 board = new char[h][w];
 visited = new boolean[h][w];
 for(int j = 0; j < h; j++){
 board[j] = sc.nextLine().toCharArray();
 }
 int answer = 0;
 for(int i = 0; i < h; i++){
 for(int j = 0; j < w; j++){
 if(board[i][j] == '#' && !visited[i][j]){
 dfs(i, j);
 answer++;
 }
 }
 }
 System.out.println(answer);
 }
 sc.close();
 }
 private static void dfs(int x, int y){
 visited[x][y] = true;
 for(int i = 0; i < 4; i++){
 int nx = x + dx[i];
 int ny = y + dy[i];
 if(nx >= 0 && nx < h && ny >= 0 && ny < w && board[nx][ny] == '#' && !visited[nx][ny]){
 dfs(nx, ny);
 } 
 }
 }
 }
정리

99클럽 코테 스터디 33일차 - dfs

댓글